問題タブ [string-search]

テキスト内の特定のパターンを見つける方法を探しています。たとえば、次のような形式のテキストからすべての参照を検索したい場合:

• Baron, Naomi (2000) Alphabet to Email: How Written English Evolved and Where It's Heading, Routledge: London and New York.

したがって、これに似たものは入力テキストから返されます。これに適したアルゴリズムはありますか。これまでに見つけたのは、テキスト内の類似した文字列を検索するためのアルゴリズムだけでした。

正規表現を使用することを考えていましたが、それが最善の方法であるかどうかはわかりません。類似性のインデックスを計算し、最高のスコアを持つヒットを返すものが必要になるためです。

ビットのテキスト内のビットのパターンを見つける文字列検索アルゴリズムを実装する必要がありました（一致はバイト/ワードで整列されていない可能性があります）。手始めに、ボイヤームーアアルゴリズムを実装しましたが、個々のビットの比較は私の目的には遅すぎました。そこで、代わりに、このペーパーで説明されているようにバイト/ワード全体を比較するブロックベースのバージョンを実装しようとしましたが、複雑になり、管理できなくなりました（一部、自分が何をしているかを完全に理解していないため）。

誰かがそのようなアルゴリズムの良い実装を持っていますか？

私の特定のユースケースは、パターンの長さN >= 32、テキストウィンドウ2N、およびビットがintsにパックされている場合です。この場合もN、charサイズの倍数ですN % 8 == 0。ボイヤームーア文字のように、私は1回前処理し、テキストの変更に何度も使用します。最初の試合は私が必要とするすべてです。パフォーマンスが重要です。

編集： Blocked Boyer-Mooreアルゴリズムの実装に成功した後、改善が見られないことに気付きました（ビットごとのバージョンの方が高速です！）これはおそらく私自身の間違いです。多くのコメント行がなければ意味がありませんが、それでも遅いです。こちらです。

100万（非常に大きい）のセットを考えると、いいえ。URLの。リストから「最初の」「一意の」URLを見つけます。

私のアプローチ：完璧なハッシュ関数を使用してハッシュを作成します。しかし、私の質問は、大きなデータをハッシュすることは不可能です。それでは、どうすればこの質問を解決できますか。

インプレースで行う方法はありますか？助けてください。前もって感謝します。

私はこのような人間の辞書ファイルを持っています(そのリストには10 億eng.dic近くの単語があるイメージ)。また、さまざまな単語のクエリを頻繁に実行する必要があります。

「foo-bar」などの文字列があります。そのファイルを検索して存在するかどうかを確認するより良い（より効率的な方法）はありますか。存在する場合は存在し、存在しない場合は辞書ファイルを追加します

Pythonに組み込みの検索機能はありますか? または、オーバーヘッドをあまりかけずにそのような検索を実行するためにインポートできるライブラリはありますか?

面接で質問がありましたが、答えられません。

質問は：

すべてのノードが文字である有向グラフが与えられ、文字列の配列も与えられます。タスクは、グラフを検索して、配列内のすべての文字列の頻度を計算することです。

私のアプローチ：トライ、サフィックスツリーを使用しましたが、インタビュアーは完全に満足していません。与えられた問題のアルゴリズムを教えてください。

Boyer-Moore 文字列検索アルゴリズムのシフト ルールを理解しようとしてきましたが、理解できませんでした。私はウィキペディアでここを読みましたが、それは複雑すぎます!

誰かがルールを簡単な方法でリストアップしてくれると、非常に役に立ちます。

文字列/部分文字列の検索を高速化するために、大きな PDF ドキュメントからある種の「文字列カタログ」を作成する必要があります。

メカニズムは次のように動作するはずです。PDF スキャナーは PDF ドキュメントをスキャンして文字列を探し、カタログ内のコールバック メソッドを呼び出してその文字列にインデックスを付けます。

では、このようなカタログを作成するには、どのような手法を使用すればよいでしょうか? 聞いたことがあります: - サフィックス ツリー - 一般化されたサフィックス ツリー - サフィックス配列

私は主に一般化された接尾辞ツリーの傾向があります。私は正しいですか、それとも間違っていますか？「通常の」接尾辞ツリーは、単一の文字列のインデックス作成にのみ適していると思います。

しかし、サフィックス配列はどうでしょうか? 一般化されたサフィックス配列はありますか?

文字列からサフィックス ツリーを構築するための C/C++ のコードをたくさん見つけましたが、一般化されたサフィックス ツリーを構築するためのコードはありません!

大文字と小文字を区別して IN 句を動作させる方法を知っている人はいますか? 文字列検索に COLLATE を LIKE で使用できることは確認しましたが、IN で使用できるかどうか、またはどのように使用できるかはわかりません。たとえば、次のようなことをしたい

そして、トピックが「食べ物」であるページを返したいのですが、トピックが「食べ物」であるページは返さないでください。これは現在、このクエリで発生しています。ありがとう。

段落内の特定のフレーズを検索し、その段落内でフレーズを中括弧で囲むプログラムを作成しました。ボイヤームーアのアルゴリズムを検索目的で使用しました。同時に、プログラムのパフォーマンスを向上させる必要もあります。必要な出力が得られましたが、パフォーマンスは悲惨です。

コードは次のとおりです。

プログラムのパフォーマンスを向上させるために、何を実装または実行できますか? 別の文字列検索アルゴリズムに切り替える必要がありますか?

誰かがこれで私を助けることができたら？