問題タブ [string-search]

特定の単語を検索する効率的な方法を探しています。switch/case、int / string.IndexOf（'！'）;を使用しますか？foreachループ/含む？

クライアントから受信している文字列があります。だから、私が得るとしましょう：

そのメッセージに対応する可能な値の配列があります。（これは構文的に正しくないので、アイデアが得られます）：

基本的に知りたい

配列内の単語を使用して、文字列xを検索したいと思います。C＃でこれを行うための最も効率的な方法は何でしょうか？文字列内の正確な位置ではなく、ブール応答が必要です。

答え

これが私が使ったものです：

Rabin-Karp 検索アルゴリズムは正常に動作していますが、再帰検索に変更する際に誰かが私を導くのを手伝ってくれますか? http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html . 例えば：

再帰的なテキスト一致検索のための他の高速なアルゴリズムはありますか?

解決

http://johannburkard.de/software/stringsearch/から外部ライブラリをビルド パスに追加します。以下のコードは、一致のすべての開始位置を返します。match1 や match2 などの組み込みのものも含まれます。

特定の文字列について、多数のファイル (つまり、600 個のファイル、それぞれ 0.5 MB) を検索する必要があります。

私はJavaを使用しているので、答えはJavaライブラリにするか、最悪の場合、Javaから呼び出すことができる別の言語のライブラリにすることをお勧めします。

ファイル内で見つかった文字列の正確な位置を返すには、検索が必要です (したがって、たとえば Lucene は問題外のようです)。

検索をできるだけ速くする必要があります。

編集開始:

ファイルは異なる形式 (つまり、EDI、XML、CSV) を持ち、かなりランダムなデータ (つまり、数値 ID など) を含む場合があります。これが、索引ベースの検索エンジンを事前に除外した理由です。

ファイルは、類似しているが異なる文字列を複数回検索されます (つまり、長さと形式が類似している ID を検索しますが、通常は異なります)。

編集終了

何か案は？

以下に、独自のルーティング デバイスからの 32b メモリ ダンプ内の文字列 'octeon' からの一致の小さな抜粋を示します。ご覧のとおり、行末から 16 文字までの調整された ASCII、次に 4 つの 32 ビット ワード (もちろんそれぞれ 8 文字)、そしてアドレス オフセットが含まれています。

そのデータにはいくつかの有用な情報が含まれていますが、残念なことに、オペレーティング システム ( HiveOS ) は連続してメモリを割り当てたり、異なるヒープを結合しようとはしません (そして、なぜそうすべきなのでしょうか?)。したがって、メモリの大部分はまだ不毛です。 -malloc されたヒープ。

任意の正規表現パターンに一致する特定のサイズの文字列を迅速かつ効率的に引き出したい ([a-zA-z]頭に浮かぶ) 自然に、永続的なオブジェクト ダンプ検査のお気に入りの 'strings' を実行すると結果が得られると考えるかもしれませんが、mdユーティリティは残酷な愛人 -- ASCII コード化された 16 進数のバンクとアドレスが存在するため、すべての行が「文字列」を含むものとして識別されます。

for line in hexdump: f.write(line[-16:])確かに、簡単なスクリプト ソリューション ( + )が存在することは誰もが知っていますgrep '[A-z]' f。

しかし、ときどき、自分の使いやすい新しいプログラミング言語にこっそり戻るよりも、これらのひどく抑圧的でありながら誤解されている正規表現をよりよく理解するようになるべきだという気持ちに襲われます。開発ツールチェーン全体をさまざまなストリーム エディターと Awk スクリプトの正規表現に完全に置き換えるまでは、本当の Unix の首ひげを生やし始めることはできないと本当に感じています。

[a-zA-z]行末から特定の数の文字 (私の場合は 16) 内でどのように一致するのですか? {16} と、それ以外の場合、ここ数分で私にとって意味のあることはすぐに失敗しました。

クワッドダンプを使用して、フリーベース検索APIのローカルバージョンを構築しようとしています。名前を照合するためにどのアルゴリズムを使用しているのでしょうか。例として、freebase.comにアクセスして「ハイキング」と入力すると、次のようになります。

• 「アポハイキング協会」
• "ハイキング"
• 「ジョージア州のハイキング」
• 「バージニアの国有林のハイキング」
• "ハイキングコース"

インドの都市の名前が約 8000 あるアプリケーションを開発しています。ユーザーが i と入力すると、オートコンプリートを使用して、ユーザーが仕事をするのを助けます。しかし、一部の都市名の綴りは、他の州の人々には推測しにくいものです。したがって、オートコンプリートには、デフォルトで提供される完全一致ではなく、おおよその文字列一致が必要です。

たとえば、次のような名前があります。

• ティルマイライ
• サーネトゥール
• ティルトゥライユル
• ティルヴァルル

また、

• ティルネルベリ
• ティルマンガラム

ユーザーが都市「ティルネルヴェリ」を検索し、テキスト ボックスに「ティルネル」と入力すると、オートコンプリート テキスト ビューに名前が表示されず、文字列が完全に一致します。

オートコンプリートドロップダウンリストでおおよそ一致する文字列を取得するにはどうすればよいですか..

XML文字列があります

「Sally Van Heerden」や「Tygervalley」などの検索語を使用して、この xml 文字列を検索したいと思います。

この文字列内の用語を見つけるために正規表現を使用する方が速いですか、それとも Python の find() メソッドは十分に速いですか? また、Python の要素ツリー XML パーサーを使用して検索し、XML ツリーを作成してから検索することもできますが、遅すぎるのではないかと心配しています。

上記の3つのうち、最も速いのはどれですか? また、他の提案はありますか？

要素が必ずしも隣接している必要はありませんが、N 文字以内で発生する必要がある部分列を文字列で検索しているとします。そう、

この比較を実行する効率的なデータ構造/アルゴリズムを探しています。内部ワイルドカードのすべての有効な組み合わせを検索するなど、いくつかのアプローチを考えることができます。

複数文字列検索アルゴリズム (おそらくAho–Corasick ) のいずれかを使用していますが、より良い解決策があるかどうか疑問に思っています。

ある方法でpdfファイルから文字列を検索したいstrstr()。しかし、pdf がプレーン テキストとして読み取られると、理解できないジャンクが生成されます。どうすればいいのですか？

pdflibには解決策があるのか​​もしれませんが、私のホスティング プロバイダーはインストールを手伝ってくれません。

これは一致します

John Smith John B Goode

次の場合に備えて、この正規表現を変更しようとしています。

いくつかのテキストの前に12359 (John B? Goode) 10249?

つまり、名前は、文字列の末尾の数字の後に、オプションで末尾の最後の数字の前に来ることがあります。

私が試してみました

しかし、それは機能しません

1. ^|[0-9]+行頭ではなく数字のみに一致する
2. グループは常に空の文字列で、次のようなものに一致しますsometext 12354(最初の数字は行末にある必要はありません。

アップデート

これはすべて橋の下の水です。データ行の最後にさらに名前が見つかったため、これは機能しません。

しかし、私の問題の解決策は、グループに OR を投げることではありませんでした。