1

文字列検索の問題があり、それを実装する方法について 2 つのアイデアが思い浮かびました。どの方法がより効率的なパフォーマンスをもたらすか、またはより良い方法を提案してくれるかどうかを人々が示すことができるかどうか疑問に思っていましたか?

問題は、次の形式のデータを含む約 450kb のテキスト ファイルがあることです。

description1, code1\n
description2, code2\n
description3, code3\n
...

カンマで区切られた 2 列のデータで、各レコードは説明コードで構成されます。

コードは短い 3 文字のテキストであり、ユーザーにとってすぐには意味をなさないため、コードと対になった説明データが存在します。

説明データは、コードの意味をユーザーに説明する短い文です。

ユーザーが編集可能なテキスト フィールドに検索キーワードを入力し、それを使用して説明データを検索できる GUI を作成しようとしています。次にシステムは、フィルター処理されたすべてのレコード、つまり、キーワードを部分文字列として持つすべての説明データと、ユーザーが選択するためにペアになっているコードを返します。これは、ユーザーが入力する文字ごとに発生します。

この機能を実装する方法について頭に浮かんだ最初のアイデアは、 などの説明データをキーとしてキーと値のペアのコレクションを作成し、NameValueCollection次に foreach ループを使用して各レコードを調べ、キーを検索することです一致する部分文字列。

2 番目のアイデアは、テキスト ファイル全体を 1 つの長い文字列に読み取り、String.IndexOf()メソッドを使用してキーワードを検索し、検索でヒットした場合は、レコードのその部分を抽出してユーザーに返すことです。

2 番目のアイデアが頭に浮かんだのは、最初のアイデアがパフォーマンスに与える影響を懸念していたからです。IndexOfで使用されているメソッドは、Boyer-Moore 文字列検索アルゴリズムよりもパフォーマンスが優れていると読んだStringComparison.Ordinalので、この方法で実装するとパフォーマンスが向上すると思いますか?

キーの部分文字列を検索する場合、ファイル全体を文字列として保存するか、NameValueCollection に保存する方が高速に取得できますか?それとも、これを行うためのより良い方法はありますか?

4

1 に答える 1

2

まったく同じ部分文字列を検索する予定の文字列のコレクションが多数ある場合は、多くのオプションを利用できます。

1 つのオプションは、Aho-Corasick 文字列マッチング アルゴリズムを使用して、ファイルのすべての行で検索クエリを検索することです。これを実行する合計実行時間は O(m + n + z) になります。ここで、m はクエリの長​​さ、z は一致の合計数、n はファイル内のすべての文字列の合計文字数です。 .

より良いがより複雑なオプションは、ファイルのすべての行から一般化されたサフィックス ツリーを構築することです。次に、一致するすべての行を時間 O(n + z) で見つけることができます。ここで、n は検索するパターンの長さであり、z はファイル内の行の総数です。これには、O(m) の前処理時間が必要です。ここで、m はファイル内の合計文字数です。これは最初のオプションよりもはるかに高速ですが、サフィックス ツリーの構築アルゴリズムはかなり複雑であるため、おそらく適切なサフィックス ツリー ライブラリを見つける必要があります。

お役に立てれば!

于 2012-12-08T00:06:08.930 に答える