問題タブ [string-search]

100 万を超えるアイテム (潜在的にはそれ以上) を保持する文字列 (任意の長さ) のデータベースがあります。

ユーザーが指定した文字列をデータベース全体と比較し、存在する場合は同一の文字列を取得するか、最も近いあいまい一致 (60% 以上の類似性) を返す必要があります。検索時間は、理想的には 1 秒未満である必要があります。

私の考えは、長さに基づいてデータベースから候補を絞り込んだ後、各データベース文字列を検索文字列と比較するために編集距離を使用することです。

ただし、この操作を頻繁に実行する必要があるため、db 文字列のインデックスを構築してメモリに保持し、db を直接ではなくインデックスをクエリすることを考えています。

この問題に別の方法でアプローチする方法、またはメモリ内インデックスを構築する方法についてのアイデアはありますか?

C++ を書くときは、Vim と Visual Studio 用の Vim プラグインを使用します。を呼び出すたびに、関数内の文字列を検索したいと思うことがよくありますobject->public_member.memberfunc()。

Vimは 1 つの単語を検索する便利な方法を提供していることを私は知ってい*ます。上記のような長い文字列のすべてのインスタンスを検索しようとすると、 after を再入力するのに時間がかかります。#//

セレクションを検索する方法はありますか？たとえば、 で強調表示してvから でコピーしy、 の後に貼り付ける方法はあり/ますか? もっと簡単なショートカットはありますか？

table_a table_b table_c文字列の列数がランダムなinを検索するにはどうすればよいですか？

これは適切なSQLではないことはわかっていますが、次のようになります。

SOコミュニティのために事前にタイ

ボイヤームーアアルゴリズムが最悪の場合の線形であるためには、不一致テーブルの計算はO（m）でなければなりません。ただし、単純な実装では、すべての接尾辞O（m）がループされ、その接尾辞のすべての位置が等しくなるかどうかがチェックされます...これはO（m ³）です。

以下は、テーブル作成アルゴリズムの単純な実装です。したがって、この質問は次のようになります。このアルゴリズムの実行時間をO（m）に改善するにはどうすればよいですか？

心を休めるために、これは宿題ではありません。誰かが改善のためのアイデアを投稿したときに改訂を追加します。

この質問は間違っているかもしれませんが、私がやりたいことは次のとおりです。

何百行もの長さになる可能性のある大きな文字列を指定すると、単語を正確に一致および置換し、他の文字列のどの部分も置換および一致しないことを確認します。

例えば ​​：

出力

単語境界を使用して正規表現を使用しようとしましたが、これ'whichwhillerrorMacO'は最後の行で発生します。

また、クラスとさまざまな区切り記号を使用してStringTokenizer単語を置き換えようとしましたが、置き換えようとしている単語の一部にこれらの区切り記号が含まれています。

この問題を解決する正規表現はありますか?

Boyer-Moore などの通常の文字列検索アルゴリズムで使用できる Python コードがあります。これを漢字で使用しようとしていますが、同じ実装ではうまくいかないようです。アルゴリズムを漢字で動作させるにはどうすればよいですか? 私はこれを参照しています：

http://en.literateprograms.org/Boyer-Moore_string_search_algorithm_(Python)#参考文献

一連のバイナリ ファイルがあり、それぞれにファイルの末尾近くに埋め込まれた文字列が含まれていますが、場所は異なります (各ファイルで 1 回だけ発生します)。文字列の場所からファイルの最後までファイルの一部を抽出し、それを新しいファイルにダンプする必要があります。

例えば。ファイルの内容が「AWREDEDEDEXXXERESSDSDS」で、対象の文字列が「XXX」の場合、必要なファイルの部分は「XXXERESSDSDS」です。

bashでこれを行う最も簡単な方法は何ですか?

2つの文字列検索アルゴリズムの場合：KMPと接尾辞木。どちらの場合に優先されますか？いくつかの実用的な例を挙げてください。

テキストのチャンク内の文字列の出現回数をカウントするための最も効率的な (または一般的に使用される) アルゴリズムは何かに興味があります。

私が読んだことによると、Boyer-Moore 文字列検索アルゴリズムは文字列検索の標準ですが、出現回数を効率的にカウントすることが文字列を検索することと同じかどうかはわかりません。

Pythonでは、これが私が欲しいものです:

編集: python がそのようなstr.count方法として機能するようです。ただし、使用するアルゴリズムを見つけることができません。

6つのcsvスタイルのファイルと2つの不適切にレイアウトされた.txtレポートからデータを抽出し、出力CSVを作成するプロセスを構築しています。また、空白を何千回も検索するオーバーヘッドが発生することを十分に認識しています。しかし、約50,000レコードの変換に12時間かかるとは思っていませんでした。

私の手動マッチングコードの抜粋（私がそのようなトークンのリストを使用するのは恐ろしいことですが、それは私が考えることができる最高のものでした）：

基本的に、効率的な文字列検索（Boyer-Mooreなど）でどのように機能するのか疑問に思っています。私のスキャナーidはスキャンしてjava.util.Stringいます。ここでの検索は比較的小さなファイルで何千回も実行されているため、メモリにバッファリングするとI/Oが減少します。BufferedReader（FileReader（File））のスキャンと比較した場合のパフォーマンスの向上はおそらく1％未満でしたが、プロセスにはまだ長い時間がかかっているようです。

また、実行を追跡しましたが、全体的な変換プロセスの速度は、ルックアップメソッドの最初と最後のように間違いなくあります。実際、ショートカットプロセスを実行して、.csvスタイルのファイル内のさまざまな識別子の出現回数をカウントし（2つのルックアップ方法を使用していますが、これはそのうちの1つにすぎません）、プロセスは約4つの異なるインデックス作成を完了しました。 1分以内に50,000レコードの識別子。12時間と比較すると、それは瞬時です。

いくつかのメモ（2010年6月6日更新）：

1. tokensBeforeのパターンマッチング動作がまだ必要です。
2. 必要なすべてのID番号は、必ずしも行の固定位置から始まる必要はありませんが、IDトークンの後に対応するオブジェクトの名前が続くことが保証されています。
3. 理想的には、結果の開始位置ではなく、文字列をintなどとして返したいと思います。

検索ごとに1ミリ秒節約できたとしても、私を助けるものは何でも役立つので、すべての入力に感謝します。ありがとうございました！

使用シナリオ1：ファイルAにオブジェクトのリストがあり、古いスタイルのシステムではファイルAにはないID番号があります。ただし、別のcsvスタイルのファイル（ファイルB）にある可能性があります。まだ.txtレポート（ファイルC）にあり、それぞれにここでは役に立たない他の情報がたくさん含まれているため、ファイルBでオブジェクトのフルネーム（2番目の列にあるため1トークン）を検索する必要があります。任意の行の）、最初の列はID番号である必要があります。それでも問題が解決しない場合は、ファイルCでそれらのトークンを検索する前に、検索トークンを空白で分割して個別のトークンに分割する必要があります。

一般化されたコード：

objectNameトークンはすべて大文字で、スペース（人の名前）で区切られたハイフンまたはアポストロフィが含まれている可能性があります。

aioobeの回答に従って、定数検索トークンの正規表現を事前にコンパイルしました。この場合は、これは単なる\r\nです。気づいたスピードアップは、私がコンパイルした別のプロセスで約20倍[0-9]{1,3}\\.[0-9]%|\r\n|0|[A-Z'-]+でしたが、上記のコードでは気づいていませんでした\r\n。これらの線に沿って作業していると、私は疑問に思います：

\r\n[^ ]とにかく使用可能な唯一の一致が非スペース文字で始まる行にある場合、私が一致する方が良いでしょうか？_matchの実行回数を減らすことができます。

もう1つの可能な最適化は、これです。すべてのtokensAfterを連結し、(.*)事前に配置します。これにより、コンパイルされる正規表現（とにかくすべてリテラル）の数が約2/3削減され、すべての行から「潜在的なトークン」を保持する代わりに、そのグループからテキストを引き出すことができます。その上のID。それもやりがいがありますか？

findWithinHorizo​​nを呼び出した後、java.util.Scannerに現在のトークンより前のトークンを返すようにできれば、上記の状況は解決できます。