問題タブ [string-matching]

各単語間にギャップがない長い一連の音から単語のインスタンス (音の文字列) を分離する必要がある音声認識エンジンをモデル化しようとしています。電話のストリームは、文字の置換/挿入/削除により認識が不十分な可能性があるため、おおよその文字列の一致を行う必要があります。

ただし、マッチングを音声学的に動機づけたい。たとえば、"m" と "n" は音声学的に類似しているため、"m" と "k" に比べて "m" の "n" への置換コストは小さくする必要があります。 "。したがって、[mein] "main" を検索している場合、文字列 [meim] "maim" はコスト 0.1 と一致し、文字列 [meik] "make" と一致します。 、コスト 0.7。同様に、各文字を挿入または削除するためのコストも異なります。文字のペア (x,y) ごとに、x を y に置き換えるコストを与える混同行列を提供できます。ここで、x と y は任意の文字または空の文字列です。

などの近似マッチングを行うツールがあることは知っていますが、agrep私が知る限り、それらは混同行列を入力として取りません。つまり、挿入/置換/削除のコスト= 1 です。私の質問は、混同行列との近似マッチングを行うことができるオープンソース ツールが既に利用可能であるかどうかです。そうでない場合、実装できる優れたアルゴリズムは何ですか?これを達成するには？

編集: 明確にするために、[mein] などの単語のおおよそのインスタンスを [aiammeinlimeiking...] などの長い文字列から分離しようとしています。理想的には、アルゴリズム/ツールは、コスト 0.0 (完全一致) の [mein]、コスト 0.7 (ほぼ一致) の [meik] などのインスタンスを、コストが特定のしきい値を下回るすべての近似文字列一致について報告する必要があります。

巨大なテキストファイルの文字列バッファがあります。文字列バッファ内の特定の単語/フレーズを検索する必要があります。それを行うための効率的な方法は何ですか？

再モジュール一致を使用してみました。しかし、私は巨大なテキストコーパスを持っているので、それを検索する必要があります。これにはかなりの時間がかかります。

単語とフレーズの辞書が与えられます。

各ファイルを繰り返し処理し、それを文字列に読み込み、辞書内のすべての単語とフレーズを検索し、キーが見つかった場合は辞書内のカウントをインクリメントします。

私たちが考えた小さな最適化の1つは、最大単語数のフレーズ/単語の辞書を最小に並べ替えることでした。次に、文字列バッファからの各単語の開始位置を比較し、単語のリストを比較します。1つのフレーズが見つかった場合、他のフレーズは検索されません（最も長いフレーズと一致したため、これが必要です）

誰かが文字列バッファで単語ごとに移動する方法を提案できますか？（文字列バッファを単語ごとに反復します）？

また、これで実行できる他の最適化はありますか？

Lucene ファジー マッチングは、基本的な editDistance アルゴリズムを使用してファジー マッチングを実装します。他の類似性メトリックを使用する Lucene のあいまい一致の他の実装はありますか? 同音異義語も特定する必要があります。また、lucene のさまざまなファジー マッチング アプローチを比較してください。

管理者がそれらをクリーンアップできるようにするために、一連のフィールドでほぼ重複する値を見つけようとしています。

私が一致している2つの基準があります

1. 一方のストリングはもう一方のストリングに完全に含まれており、その長さの少なくとも 1/4 です。
2. 文字列の編集距離は、2 つの文字列の合計の長さの 5% 未満です。

疑似 PHP コード:

可能な限り、比較的高価なstriposおよびlevenshtein関数の呼び出しを減らすようにしました。これにより、実行時間がかなり短縮されました。ただし、O(n^2) 演算として、これはより大きな値のセットに対応できず、配列を単純に反復処理するだけでかなりの量の処理時間が費やされているようです。

操作されている値のいくつかのセットのいくつかのプロパティ

基準をチェックする時間を短縮するために他にできることはありますか。さらに重要なことに、必要な基準チェックの数を減らす方法はありますか (たとえば、入力値を前処理することによって)。選択率が低い？

編集：実装されたソリューション

文字列が月の名前であるかどうかを判断したいのですが、比較的迅速に実行したいと考えています。現在私の脳に詰まっている機能は次のようなものです。

ただし、大量のテキストを処理し、一度に 1 つの文字列をこの関数に渡します。ほとんどの場合、ループ全体を通過して false を返すという最悪のケースになります。

この状況に適応できる月名と年に一致する正規表現について話している別の質問を見ました。正規表現の方が速いでしょうか? もっと速いかもしれない他の解決策はありますか？

JPQL を類似の文字列に一致させるには、どのような方法がありますか?

同様に、私は意味します：

• 含む: 検索文字列は、一致するエンティティの文字列内で見つかります
• 大文字小文字を区別しません
• 小さなスペルミス: 例: "arow" は "arrow" と一致します

最初の 2 つは簡単だと思いますが、最後の 1 つは助けていただければ幸いです

ありがとうございました

2 セットの楽曲を比較する必要があります (つまり、MIDI 形式で取得したノートの詳細を抽出してデータベース テーブルに保存したものと、XML 形式で取得した楽譜) を比較する必要があります。楽譜に対する演奏を評価する場合 (ピッチ、デュレーション、リズムなどのノートの詳細)、参照 (楽譜) ノートからの見逃し/余分な/間違った/交換されたノートを識別するために、ノートの配置を行う必要があります。

私は約 1800 から 2500 のノートを 1 つのピースに持っています (ポリフォニックではさらに多くなる可能性があります。今はモノフォニックでやっています)。これらすべてを配列に入れる必要がありますか？メモリの過負荷またはスタック オーバーフローでしょうか。

KMP、Boyce-Moore などの文字列一致アルゴリズムがあります。ただし、動的計画法を使用して音符を揃えることもできます。動的計画法を使用してこれにアプローチするにはどうすればよいですか? 利用可能なアルゴリズムは何ですか? おおよその文字列一致についてですか？

生産性が高いのはどのアプローチですか? Boyce-Moore のような文字列マッチング アルゴリズム、または動的プログラミング? どちらがより効果的かをどのように評価できますか？

洞察や提案を大歓迎します 事前に感謝します

1.不一致 (誤って演奏された音符)、2.挿入 (追加で演奏された音符)、および 3.削除 (失われた音符) を参照に対して楽曲 (たとえば、テーブルに保存された音符ピッチ [文字列値]) で見つける必要があります。音楽作品。

これは、正確な文字列一致アルゴリズムまたは動的プログラミング/近似文字列一致アルゴリズムによって可能です。ただし、メモの不一致、挿入、削除を識別するため、おおよその文字列一致が問題に適していることに気付きました。または、約をサポートするための Boyer-moore の拡張バージョン。文字列マッチング。

おおよその文字列一致を試すことができるサンプル Java コードへのリンクはありますか? 複雑な説明や方程式を見つけましたが、いくつかのサンプル コードと簡単な説明でうまくいくことを願っています。または、boyer-moore でサンプルの Java コードを見つけることができますか? 文字列一致？ボイヤームーアの概念は理解できますが、約 1000 をサポートするように調整するのに苦労しています。文字列の一致 (つまり、不一致、挿入、削除をサポートするため)。

また、最も効率的なものは約です。文字列マッチング アルゴリズム (正確な文字列マッチング アルゴリズムのボイヤー ムーアのような)?

洞察/提案をいただければ幸いです。よろしくお願いします

これは、「アルゴリズムの設計と分析の概要」の演習です。文字列の一致の問題です。文字列 ABCD があり、パターン XY があるとします。文字列にパターンが含まれているかどうかを確認したい。

ここでは力ずくの使用を想定しているだけなので、左から右への比較では A と X を比較し、次は B と X を比較します。右から左への比較では B と Y を比較しますが、次は C を比較します。ヒントは、右から左への比較には利点があると言っていますが、その理由はわかりません。

どんなヒントでも大歓迎です！

次の行を見つけるために使用できる正規表現が必要です。

それらを次の行に置き換えます。

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