performance - 二分探索のために文字列の定数セットを前処理する

Question

複数の文字列 (サイズ = K < 1000) の並べ替えられたリストがあります。ソートされたリスト内の数十億 (サイズ = N) の文字列の挿入位置を見つける必要があります。リストは一定に保たれ、文字列は子ノードに挿入されます。

質問は: 私は現在二分探索を使用しており、その時間コストは O(strlen * NlogK) です。しかし、ソートされたリストは一定であるためです。logK よりも検索を高速化するために、小さなソート済みリストに前処理方法があるのだろうか?

Answer 1

いくつかの適切な代替手段には、トライ(おそらくパトリシア トライまたは三分探索木として実装されている)、または完全なハッシュ テーブルが含まれます。

編集:トライを使用して一致しない文字列の「挿入位置」を見つけるには、最初に各完全な文字列にその位置のラベルを付けます(最初にトライを構築するときにこれを行うことができます)。一致しない文字列を検索すると、一致しない文字列内の最初のインデックスでこれが検出されます。

たとえば、CANNOT と CATASTROPHE を含むトライで文字列 CAR を探していたとします (他に関連するものは何もありません)。A の下に R の子がないため、この不一致は R で検出されます。しかし、その位置の周囲の文字が N と T であることが簡単にわかるはずです。N に移動してから、下と右に進むと、位置を読み取ることができる場所に連れて行ってください。または、T に移動してから下に進み、左に進むと、CATASTROPHE が発生します。