問題タブ [levenshtein-distance]

これらすべてを 1 つのクエリに移動するにはどうすればよいでしょうか? すべての用語を照会して、PHP でフィルタリングを行う必要はありません。

これは、文字列を最小限の操作で回文に変換するための問題の状態です。レーベンシュタイン距離に似ていることは知っていますが、 まだ解決できません

たとえば、入力mohammadsajjadhossainの場合、出力は8です。

同じ長さの2つの文字列が与えられた場合、レーベンシュタイン距離により、最初の文字列が与えられた場合に、2番目の文字列を取得するために必要な変換の最小数を見つけることができます。ただし、すべて同じ方法で生成された文字列の複数のペアのアルゴリズムを調整する方法を見つけたいと思います。

私は大量のクエリを持っており、levenshtein を使用してタイプミスを計算しています。現在、levenshtein により mysql がフル CPU 時間を消費しています。私のクエリは、UNION ステートメントの全文検索 + レーベンシュタインです。sql1 は私の現在のクエリです。sql2 は高速で CPU 時間をあまり使用しない全文検索のみです。

タイプミスを取得する別の方法を持っている人はいますか? データの正規化に答えないでください、私はそれを考えましたが、一致/計算を事前に作成してインデックス付きの別のテーブルを作成できないため、私のデータには適用できません。

更新3

終わり。以下は、最終的にすべてのテストに合格したコードです。繰り返しになりますが、これはMuriloVasconceloによるSteveHanovのアルゴリズムの修正バージョンをモデルにしています。助けてくれたすべてに感謝します！

更新2

最後に、ほとんどのテストケースでこれを機能させることができました。私の実装は、実際には、MuriloのC++バージョンのSteveHanovのアルゴリズムからの直接翻訳です。では、このアルゴリズムをどのようにリファクタリングしたり、最適化したりする必要がありますか？以下はコードです...

この質問に貢献してくれた皆さん、ありがとうございました。Levenshtein Automataを動作させようとしましたが、実現できませんでした。

したがって、上記のコードに関するリファクタリングや最適化に関する提案を探しています。混乱があれば教えてください。いつものように、必要に応じて残りのソースコードを提供できます。

更新1

そこで、単純なTrieデータ構造を実装し、Steve HanovのPythonチュートリアルに従って、レーベンシュタイン距離を計算しようとしました。実際、私は特定の単語とTrie内の単語の間の最小レーベンシュタイン距離を計算することに興味があるので、 MuriloVasconcelosのバージョンのSteveHanovのアルゴリズムに従っています。うまく機能していませんが、これが私のTrieクラスです。

...およびTrieNodeクラス：

Murilo Vasconcelosが持っているように検索を実装しようとしましたが、何かがおかしいので、これをデバッグするのに助けが必要です。これをリファクタリングする方法や、バグがどこにあるかを指摘する方法について提案してください。最初にリファクタリングしたいのは「minCost」グローバル変数ですが、これは最小のものです。とにかく、ここにコードがあります...

コメントが不足していることをお詫び申し上げます。だから私は何が間違っているのですか？

初期投稿

2つの弦の間のレーベンシュタイン距離を計算する効率的な方法を理解することを期待して、「トライを使用した高速で簡単なレーベンシュタイン距離」という記事を読んでいます。これに関する私の主な目標は、大量の単語セットが与えられた場合に、入力単語とこの単語セットの間の最小レーベンシュタイン距離を見つけることができるようにすることです。

私の簡単な実装では、入力単語ごとに、入力単語と単語のセットの間のレーベンシュタイン距離を計算し、最小値を返します。動作しますが、効率的ではありません...

私はJavaでのTrieの実装を探していましたが、2つの一見良い情報源に出くわしました。

• Koders.comバージョン
• code.google.comバージョン （編集：これはgithub.com/rkapsiに移動したようです）

ただし、これらの実装は、私がやろうとしていることには複雑すぎるようです。それらがどのように機能し、Trieデータ構造が一般的にどのように機能するかを理解するためにそれらを読んでいると、私はさらに混乱するようになりました。

では、Javaで単純なTrieデータ構造を実装するにはどうすればよいでしょうか。私の直感によると、各TrieNodeは、それが表す文字列と、必ずしもすべての文字ではなく、アルファベットの文字への参照を格納する必要があります。私の直感は正しいですか？

それが実装されたら、次のタスクはレーベンシュタイン距離を計算することです。上記の記事のPythonコード例を読みましたが、Pythonについては話せません。再帰検索を実行すると、Java実装のヒープメモリが不足します。では、Trieデータ構造を使用してレーベンシュタイン距離をどのように計算しますか？このソースコードをモデルにした簡単な実装がありますが、Trieを使用していません...非効率的です。

あなたのコメントや提案に加えて、いくつかのコードを見るのは本当に素晴らしいことです。結局のところ、これは私にとっての学習プロセスです...私はTrieを実装したことがありません...したがって、この経験から学ぶことがたくさんあります。

ありがとう。

ps必要に応じて、任意のソースコードを提供できます。また、 Nick Johnsonのブログで提案されているようにBK-Treeを読んで使用してみましたが、思ったほど効率的ではありません...または私の実装が間違っている可能性があります。

地獄、

PHP には、文字列の類似性を比較できる、levenshtein、similar_text、soundex などの多くの文字列関数があります。 http://www.php.net/manual/en/function.levenshtein.php

精度とパフォーマンスに優れているのはどれですか?

レーベンシュタインのパーセンテージを決定するときに、入力文字列と一致する文字列の両方を使用する必要がある理由を説明できますか?

検索候補を作成する最速の方法を考え出そうとしています。最初は、MySQL テーブルと組み合わせた Levenstein UDF 関数が機能すると考えていました。しかし、levenshtein を使用すると、mysql はテーブル内のすべての行 (大量の単語) を調べなければならず、クエリが非常に遅くなります。

最近、Sphinx ( http://sphinxsearch.com/ ) をインストールして全文検索に使い始めました。その主な理由は、そのパフォーマンスと、SphinxSE との mysql の緊密な統合です。

そこで、スフィンクスを使用してパフォーマンスを向上させる「もしかして」アルゴリズムを実装できるかどうか自問したところ、単純なものを見つけたと思います。基本的に、修正したいすべてのキーワードを取得し、各文字の間にスペースを入れてから、スフィンクス インデックスに入れます。単語が「keyword」の場合は「keyword d」になります。ここで、ユーザーが単語を入力すると、それを文字に分割し、提供された文字のいずれかに一致するレコード (必要なのは 1 つだけ) を sphinx インデックスで検索します。最良の部分は、スフィンクスが一致した行の関連性 (重み) を計算するのに非常に優れているため、最適な一致が常に最大の重みを持つことです (私は思います)。また、単語 (私の場合は文字) の位置も考慮されるため、最適な一致はその順序になります。

sphinx クエリを使用すると、キーワード リストで最も類似した単語を取得できます。次に、再配置された文字https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distanceを説明する拡張レーベンシュタイン距離を使用して、php で確認します。文字列の距離が 2 未満 (および != 0) の場合、単語を提案します。それ以外の場合は、何も提案しないでください。

私の考えに問題はありますか？私が考えていなかった何か？スフィンクス クエリで予想される不具合や、最適な一致をもたらさないスフィンクスの関連性計算での癖はありますか? どこか間違っている場合は修正してください。

文字列 A が与えられた場合、BI は、B が A になるまでの挿入、削除、および置換の数を計算する必要があります。これに適したアルゴリズムは何でしょうか?