4

連結された文字列を含むファイルがあります。

find_or_add(string)また：

  • ファイル内の文字列のオカレンスのオフセットを返します (最初である必要はありません)
  • ファイルに文字列が含まれるのに必要なだけ、文字列の末尾をファイルに追加します (そして、ファイル内の文字列のオフセットを返します)。

疑似コード:

file.init()                // file == ""
file.find_or_add("cat")    // file == "cat", returns 0
file.find_or_add("able")   // file == "catable", returns 3
file.find_or_add("table")  // file == "catable", returns 2
file.find_or_add("tables") // file == "catables", returns 2
file.find_or_add("spigot") // file == "catablespigot", returns 7
file.find_or_add("pig")    // file == "catablespigot", returns 8

このファイルをメモリ内で「要約」し、必要な操作を最大 O(log N) で許可するには、どのアルゴリズム/構造を調べる必要がありますか?

ファイルが RAM よりも大きいと仮定します。

言語は重要ではありませんが、疑似コード、C、Java、Python、Javascript、Haskell を読むことができます。

4

3 に答える 3

1

接尾辞配列と接尾辞ツリーは、メモリの問題を引き起こす可能性があります。(すべての suffixID を構造に格納する必要があるため、特定の深さでカットしたとしても、常にテキストよりも大きくなります)。

特定のプレフィックスの ID を表す一連のファイルを作成できます。長さ 2 のすべてのプレフィックスを別のファイルに保存し、それをソートしておくとします。このファイルには、平均してサフィックス ID の 1/26^2 が含まれます。したがって、 aa.txt 、 ab.txt などのファイルがあります。ソートされたファイル内のエントリ (Suffix Array)。ルックアップを実行するたびに、この小さなファイルをロードします。このファイルは、既にソートおよびチェックされています。複雑さは O(N) になります (テキストの一定の制御可能な部分であるファイルをロードする必要があります) が、最高のパフォーマンスを得るためにプリファクタを調整できます。たとえば、5 Gb のファイルで長さ 2 のプレフィックスを使用すると、8 Mb サイズのファイルのセットができ、prefixLength 3 の場合は約 320 kb になります。

于 2013-07-19T07:01:42.650 に答える
0

これは当てはまらないかもしれませんが、このテクノロジーとアルゴリズムには O(log N) 検索、高速挿入があり、大規模なデータ セットでの効率的な IO のために大幅に最適化されています。間違っているかもしれませんが、挿入と検索のバランスが取れているように感じます。どう思いますか？

于 2013-07-18T09:07:43.707 に答える