2

私の友人はインタビューでこの問題に出くわしました。いくつかの文を含むファイルが与えられます。文には 0-9、az、AZ、ピリオド (.) しかありません。ファイルを読み取って、クエリが高速になるように保存する必要があります。このフェーズにかかる時間は問題ではありません。ここで、クエリはいくつかの単語で構成され、これらすべての単語を含む最小の部分文字列を返す必要があります。順序は重要ではありません。（注：ファイル全体がメインメモリに収まると仮定）

たとえば、ファイルが「Ram はコンピュータ サイエンスの学位を取得していました。Ram は自宅にコンピュータを持っています。Ram は現在自宅にいます。」

クエリ 1 :"Ram computer a" 出力: "Ram has a computer" クエリ 2: "Ram home" 応答: "home.Ram"

各ノードが単語で構成されるリンクリストとしてファイルを保存することを考えました。が最後の単語の場合、単語 + フルストップがノードに格納されます。クエリ時に、LL をトラバースして、すべての単語を含む最小の文字列を見つける必要があります。

どうすればさらに最適化できますか? より良い方法でファイルを保存できますか?

4

1 に答える 1

2

ファイルはSuffix arrayの形式で保存できます。ファイルの長さを N とすると、O(N) 時間で作成できます。各クエリ ワードは、バイナリ検索で O(M + log N) 時間で見つけることができます。ここで、M はクエリ ワードの長さです。Mohamed Ibrahim Aboelhodaa、Stefan Kurtzb、Enno Ohlebusch によるこの論文「Replaceing suffix trees with enhanced suffix arrays」に示されているように、これを O(M) に改善する可能性があります。

前処理フェーズにかかる時間は問題にならないため、サフィックス配列の代わりにTrieを使用できます。入力ファイルの各単語をトライに追加し、ファイル内のこの単語の位置をこの単語の位置のリストに追加するだけです (トライ ノードごとに 1 つのリストが必要です)。

すべてのクエリ単語の位置がサフィックス配列またはトライで見つかったら、それらをソートする必要があります (トライの場合はすでにソートされているため、サフィックス配列のみ)。次に、それぞれに最も近い位置のセットを見つけます。他の：

  1. すべてのクエリ ワードの最小位置を優先キューに追加します (最小ヒープとして実装される場合があります)。
  2. この優先待ち行列の先頭の単語の未処理位置のリストが空でない間、先頭の待ち行列エントリを同じ単語の次の位置に置き換えます。いくつかのエントリが優先キューに追加/削除されるたびに、対応する単語の末尾の位置を順序付けられたコレクション (二分探索木など) に追加/削除します。このコレクション内の最大のエントリと優先キュー内の最小のエントリとの差により、すべてのクエリ ワードを含む最小の部分文字列を決定できます。
于 2013-04-20T13:42:46.817 に答える