6

ファイルから文字列のリストを読み取り、それらをデータ構造に保存し、それらの文字列をプレフィックスで検索する必要があるアプリケーションを作成しています。文字列のリストは、特定の言語の単なる単語のリストです。たとえば、検索関数がパラメーターとして "stup" を取得する場合、["stupid", "stupidity", "stuor"...] を返す必要があります。O(log(n)*m) 時間で実行する必要があります。ここで、n はデータ構造のサイズ、m は結果の数であり、できるだけ高速にする必要があります。現在、メモリ消費は大きな問題ではありません。私はこれを python で書いているので、python ラッパーを使用して c で実装された (できれば) 適切なデータ構造を教えていただければ幸いです。

4

4 に答える 4

15

あなたは試してみたい。

http://en.wikipedia.org/wiki/Trie

私は Scrabble と Boggle プログラムでそれらを使用しました。あなたが説明したユースケース（高速プレフィックスルックアップ）に最適です。

Python でトライを構築するためのサンプル コードを次に示します。これは、数か月前にまとめた Boggle プログラムからのものです。残りは読者の演習として残します。しかし、接頭辞チェックの場合、基本的には、ルート ノード (変数words) から始まり、接頭辞の文字をたどって子ノードに続き、そのようなパスが見つかった場合は True を返し、それ以外の場合は False を返すメソッドが必要です。

class Node(object):
    def __init__(self, letter='', final=False):
        self.letter = letter
        self.final = final
        self.children = {}
    def __contains__(self, letter):
        return letter in self.children
    def get(self, letter):
        return self.children[letter]
    def add(self, letters, n=-1, index=0):
        if n < 0: n = len(letters)
        if index >= n: return
        letter = letters[index]
        if letter in self.children:
            child = self.children[letter]
        else:
            child = Node(letter, index==n-1)
            self.children[letter] = child
        child.add(letters, n, index+1)

def load_dictionary(path):
    result = Node()
    for line in open(path, 'r'):
        word = line.strip().lower()
        result.add(word)
    return result

words = load_dictionary('dictionary.txt')
于 2009-07-15T12:09:40.033 に答える
2

トライ(またはプレフィックス ツリー)は、あなたの路地のすぐ上で聞こえます。長さ m のプレフィックス文字列を O(m) で検索できると思います。

于 2009-07-15T12:10:52.153 に答える
-1

文字列配列。

次に、それをバイナリ検索して最初の一致を検索し、その後のすべての一致について1つずつステップスルーします

（私はもともとここにもリンクリストを持っていました...しかし、もちろんこれにはランダムアクセスがないため、これは「bs」でした（おそらく、私が反対票を投じられた理由を説明しています）.私の二分探索アルゴリズムは依然として最速の方法です.

于 2009-07-15T12:11:01.280 に答える