問題タブ [edit-distance]

レーベンシュタイン距離式のCoffeeScript実装、別名EditDistanceを作成または検索しようとしています。これが私がこれまでに持っているものです、どんな助けでも大いに感謝されるでしょう。

ところで：私はこのコードが多くのレベルで間違っていることを知っています、私はありとあらゆる建設的な批判を受けてうれしいです。改善を目指して、この公式を理解してください！

CodeEdit1：Trevorが指摘したエラーを修正しました。上記の現在のコードには、これらの変更が含まれています

更新：私が尋ねている質問は、CoffeeScriptでLevenshteinをどのように実行するかです。

これが、私が達成しようとしていることを理解するのに役立つレーベンシュタイン距離アルゴリズムの「ステップ」です。

手順
1nをsの長さに設定します。mをtの長さに設定します。n = 0の場合、mを返して終了します。m = 0の場合、nを返し、終了します。0..m行と0..n列を含む行列を作成します。

2
最初の行を0..nに初期化します。最初の列を0..mに初期化します。

3 sの各文字を調べます（iは1からnまで）。

4 tの各文字を調べます（jは1からmまで）​​。

5 s[i]がt[j]と等しい場合、コストは0です。s[i]がt [j]と等しくない場合、コストは1です。

6行列のセルd[i、j]を次の最小値に等しく設定します。プラス1のすぐ上のセル：d [i-1、j]+1。b. すぐ左のセルに1を加えたもの：d [i、j-1]+1。c. 対角線上と左のセルにコストを加えたもの：d [i-1、j-1]+コスト。

7反復ステップ（3、4、5、6）が完了すると、セルd [n、m]に距離が表示されます。

出典：http：//www.merriampark.com/ld.htm

2 つのファイル ツリー A と B が与えられた場合、 A を B に変換するために必要な操作の最短シーケンスまたは短い操作シーケンスを決定することは可能ですか?

操作は次のとおりです。

1. 新しい空のフォルダーを作成する
2. 任意の内容で新しいファイルを作成します
3. ファイルを削除する
4. 空のフォルダを削除する
5. ファイルの名前を変更する
6. フォルダの名前を変更する
7. ファイルを別の既存のフォルダー内に移動する
8. 別の既存のフォルダー内にフォルダーを移動する

A と B は、同じフォルダー構造内に同じ内容 (または同じサイズ、同じ CRC) で同じ名前の同じファイルを持つ場合、同一です。

この質問は、しばらくの間私を困惑させてきました。現時点では、次の基本的な考え方があります。

• データベースを計算します。
  • ファイル名とその CRC を保存する
  • 次に、サブフォルダーのないすべてのフォルダーを検索し、それらに含まれるファイルの CRC から CRC を計算し、それらに含まれるファイルの合計サイズからサイズを計算します。
  • ツリーを上って、各親フォルダーの CRC を作成します
• データベース A とデータベース B を持つ次のループを使用します。
  • A ∩ B を計算し、両方のデータベースからこの共通部分を削除します。
  • 内部結合を使用して、A と B で一致する CRC を見つけます。最初にフォルダーをサイズ降順で並べます
  • 結果がある間、最初の結果を使用してフォルダーまたはファイルを移動し (必要に応じて新しいフォルダーを作成する可能性があります)、結果のソース行を両方のデータベースから削除します。移動があった場合は、データベース A の新しい場所の親フォルダーの CRC を更新します。
  • 次に、データベース A で参照されているすべてのファイルとフォルダーを削除し、データベース B で参照されているファイルとフォルダーを作成します。

ただし、これは実際には最適ではない方法だと思います。何をアドバイスしてもらえますか？

ありがとうございました！

おそらくRubyでスクリプトを作成する必要があります。このスクリプトは、1ブロックのテキストを取得し、そのテキストの録音の多数の文字起こしを元のテキストと比較して、正確性を確認します。それが完全に混乱している場合は、別の方法で説明してみます...

数文の長さの台本を読んでいる何人かの異なる人々の録音があります。これらの録音はすべて、他の人によって何度もテキストに書き戻されています。私はすべての文字起こし（数百）を取り、それらを元のスクリプトと比較して正確にする必要があります。

擬似コードを概念化することすら問題があり、誰かが私を正しい方向に向けることができるかどうか疑問に思っています。検討すべき確立されたアルゴリズムはありますか？レーベンシュタイン距離が提案されましたが、句読点の選択や空白などの違いを考慮すると、これは長い文字列にはうまく対応できないようです。最初の単語が欠落していると、たとえ1つおきの単語であっても、アルゴリズム全体が破壊されます。完璧だった。私は何にでもオープンです-ありがとう！

編集：

ヒントをありがとう、psyho。ただし、私の最大の懸念事項の1つは、次のような状況です。

元のテキスト：

I would've taken that course if I'd known it was available!

転写

I would have taken that course if I'd known it was available!

Even with a word-wise comparison of tokens, this transcription will be marked as quite errant, even though it's almost perfect, and this is hardly an edge-case! "would've" and "would have" are commonly pronounced extremely similarly, especially in this part of the world. Is there a way to make the approach you suggest robust enough to deal with this? I've thought about running a word-wise comparison both forward and backward and building a sort of composite score, but this would fall apart with a transcription like this:

I would have taken that course if I had known it was available!

Any ideas?

重複の可能性:
ある順列を別の順列に変換するために必要なスワップのカウント

許可されている操作のみが2つの隣接する文字の転置である、ある種の文字列距離をカウントするアルゴリズムを探しています。例:
string1: "mother"
string2: "moterh"
distance: 2 (最初に "h" を "e" に置き換えて "motehr" を取得し、次に "h" を "r" に置き換えて "moterh"
を取得します) –レーベンシュタイン距離はその問題と非常によく似ていますが、多くのメモリが必要です (1000000 文字までの単語で非常に高速に動作することを望みます)。私はすでにこれを書いています：

文字列は char[n] として表されます。n はその長さです。私はそれをより速く行う方法があると確信しており、誰かがそれを行う方法やソースコードを書く方法を教えてくれれば非常に感謝しています (Java/Python/C++ が最適ですが、何でも素晴らしいです)。

PS 言語の間違いがあればすみません。私は英語が苦手で、まだその言語を習得していません。

与えられた2つの文字列sとt。s編集距離（レーベンシュタイン距離）からの各部分文字列を見つける必要がありますt。i実際には、位置ごとに、位置でs開始されるすべてのサブストリングの最小編集距離を知る必要がありiます。

例えば：

そして、私は次のようなものを取得する必要があります：

{2,1,0,2,2}

説明：

等々。

もちろん、ブルートフォースアルゴリズムを使用してこのタスクを解決できます。しかし、より高速なアルゴリズムはありますか？

手伝ってくれてありがとう。

編集距離は、ある文字列から別の文字列に必要な挿入、削除、または置換の数を見つけます。このアルゴリズムにスワップも含めたいと思います。たとえば、「apple」と「appel」の編集距離は 1 にする必要があります。

スペルミスのある単語を提案するためにオンライン検索エンジンで使用される典型的なアルゴリズムは何ですか. 必ずしも Google について話しているわけではありませんが、たとえば Amazon.com など、検索機能を備えたすべてのサイトです。という単語を検索するとします"shoo"。サイトが戻ってきて言うでしょう"did you mean: shoe"。

これは、レーベンシュタイン距離アルゴリズムのバリエーションですか? おそらく、フルテキスト検索フレームワーク (たとえば lucene など) を使用している場合、これは組み込まれているのでしょうか? もしかしてフルカスタム？

答えが大きく異なることはわかっています。これを（エンタープライズ環境で）開始する方法についての指示を探しているだけです。

最も近い一致を見つけるために、コレクションに対する文字列の編集距離を計算しようとしています。私の現在の問題は、コレクションが非常に大きい (約 25000 アイテム) ことです。そのため、セットを同じような長さの文字列だけに絞り込む必要がありましたが、それでも数千の文字列に絞り込むだけであり、これはまだ非常に遅いです。同様の文字列をすばやく検索できるデータ構造はありますか、またはこの問題に対処できる別の方法はありますか?

レーベンシュタイン距離を計算しようとしていました。次のコードは、キット/フィットやシッティング/ニットなどの小さな文字列に対して機能します。しかし、日曜日/土曜日の文字列のセグメンテーション違反が発生しました。GDBを（初めて）使用した後、str2が割り当てられたメモリ空間を超えていることが問題であることがわかりました。しかし、私はその方法を理解することができませんでした。私はこれに多くの時間を費やしてきましたが、今では壁を見つめているようです。誰かが私のコードの間違いを指摘してもらえますか? ありがとうございました。

出力

スペルチェッカー モジュールを作成しようとしています。

テキストをロードし、16 mb ファイルから辞書を作成し、検出された単語が辞書の単語と類似しているかどうかをチェックします (類似 = 2 文字まで変化する) 場合は、辞書の形式に変更します。

現在、レーベンシュタイン距離アルゴリズムを使用しており、50 単語セットの処理に 3 分かかります...

より迅速な解決策が必要であると確信しています。プロファイラーによると、私のアプリは時間の 80% 以上をレーベンシュタイン距離関数に費やしています。

より良いソリューション/アルゴリズムはありますか?

私が使用するアルゴリズムの実装バージョンは次のとおりです。