4

具体的な例を挙げます。

  • あなたはアメリカのすべての名のリストを持っています。
  • GUIで補完をオートコンプリートしたい。

明らかなことは、基数木を使用して、指定されたプレフィックスの名前のリストを取得することです。ただし、これは周波数情報を考慮していません。したがって、上位5つの結果を最初の字句結果にするのではなく、最も一般的な5つの名前を指定します。

例：プレフィックスの場合dan

 (5913, 'Daniel')
 (889, 'Danny')
 (820, 'Dana')
 (272, 'Dan')
 (60, 'Dane')

私が見逃したトライツリーアルゴリズムはありますか？もちろん、理想的な実装（存在する場合）は、私の頭の中ではpythonです。

更新： Paddy3113が提案したものには概ね満足していますが、私が削減しているファイルの1つである2.6GBファイルをフィードすると、完全に爆発すると言います。詳細を調べると、出力からいくつかの洞察が得られます。

samz;Samzetta|Samzara|Samzie
samza;Samzara
samzar;Samzara
samzara;Samzara
samze;Samzetta
samzet;Samzetta
samzett;Samzetta
samzetta;Samzetta
samzi;Samzie
samzie;Samzie

# Format - PREFIX;"|".join(CHOICES).

物事の恵みの面であと数日あるので、私はまだキラーソリューションを探しています。それは削減だけでなく、物事のルックアップ側についてもあるからです。

4

5 に答える 5

4

はい、トライを使用できます。トライノードの最も頻繁な名前は、（1）そのトライノードでの名前、または（2）トライノードの子の最も頻繁な名前のいずれかです。試してみるPythonコードを次に示します。

from collections import defaultdict


class trie:
    __slots__ = ('children', 'freq', 'name', 'top5')

    def __init__(self):
        self.children = defaultdict(trie)
        self.freq = 0
        self.name = None
        self.top5 = []

    def __getitem__(self, suffix):
        node = self
        for letter in suffix:
            node = node.children[letter]
        return node

    def computetop5(self):
        candidates = []
        for letter, child in self.children.items():
            child.computetop5()
            candidates.extend(child.top5)
        if self.name is not None:
            candidates.append((self.freq, self.name))
        candidates.sort(reverse=True)
        self.top5 = candidates[:5]

    def insert(self, freq, name):
        node = self[name]
        node.freq += freq
        node.name = name


root = trie()
with open('letter_s.txt') as f:
    for line in f:
        freq, name = line.split(None, 1)
        root.insert(int(freq.strip()), name.strip())
root.computetop5()
print(root['St'].top5)
于 2012-05-30T13:59:34.487 に答える
2

チューニングについて何も考えずに、名前とその頻度のリストがあると仮定して、プレフィックスをそのプレフィックスを持つ名前のセットにマッピングする辞書を作成し、各セットを上位5つの名前のリストに変換します。周波数。

ここから派生した男の子の名前のリストを使用して、すべての行が整数の出現頻度、いくつかのスペース、そして次のような名前であるテキストファイルを作成します。

8427    OLIVER 
7031    JACK 
6862    HARRY 
5478    ALFIE 
5410    CHARLIE 
5307    THOMAS 
5256    WILLIAM 
5217    JOSHUA 
4542    GEORGE 
4351    JAMES 
4330    DANIEL 
4308    JACOB 
...

次のコードは辞書を構成します。

from collections import defaultdict

MAX_SUGGEST = 5

def gen_autosuggest(name_freq_file_name):
    with open(name_freq_file_name) as f:
        name2freq = {}
        for nf in f:
            freq, name = nf.split()
            if name not in name2freq:
                name2freq[name] = int(freq)
    pre2suggest = defaultdict(list)
    for name, freq in sorted(name2freq.items(), key=lambda x: -x[1]):
        # in decreasing order of popularity
        for i, _ in enumerate(name, 1):
            prefix = name[:i]
            pre2suggest[prefix].append((name, name2freq[name]))
    # set max suggestions
    return {pre:namefs[:MAX_SUGGEST]
            for pre, namefs in pre2suggest.items()}

if __name__ == '__main__':
    pre2suggest = gen_autosuggest('2010boysnames_popularity_engwales2.txt')

dictにプレフィックスを付けると、提案が返されます（この場合は頻度とともに、必要に応じて破棄できます。

>>> len(pre2suggest)
15303
>>> pre2suggest['OL']
[('OLIVER', 8427), ('OLLIE', 1130), ('OLLY', 556), ('OLIVIER', 175), ('OLIWIER', 103)]
>>> pre2suggest['OLI']
[('OLIVER', 8427), ('OLIVIER', 175), ('OLIWIER', 103), ('OLI', 23), ('OLIVER-JAMES', 16)]
>>>

試してみません:-)

タイムキラー

実行に時間がかかる場合は、dictを事前に計算してファイルに保存し、必要に応じてpickleモジュールを使用して事前に計算された値をロードします。

>>> import pickle
>>> 
>>> savename = 'pre2suggest.pcl'
>>> with open(savename, 'wb') as f:
    pickle.dump(pre2suggest, f)


>>> # restore it
>>> with open(savename, 'rb') as f:
    p2s = pickle.load(f)


>>> p2s == pre2suggest
True
>>>
于 2012-05-29T20:25:04.427 に答える
0

基本的に、トライの実装を拡張して、子をアルファベット順ではなく人気順に保存することができます。つまり、トライの各ノードに人気を保存する必要があると言われています。

于 2012-05-24T16:37:02.530 に答える
0

これを行う方法についてのアイデアは次のとおりです。

文字列トライを作成し、ツリー内の各ノードに整数を格納します。このノードは、そのノードを使用する名前の数を示します。したがって、名前がトライに挿入されるときに、名前のすべてのノードをインクリメントします。

次に、値が最も高い名前を貪欲に選択することで、上位の名前を判別できます。

正式には、他の文字列トライ構築アルゴリズムと同じですが、整数をインクリメントするステップが追加されています。

于 2012-05-24T19:40:20.493 に答える
0

迅速な検索が必要な場合、唯一の実際の解決策は、特定のプレフィックスの回答を事前に計算することです。データが変更されない場合はこれで問題ありませんが、読み込み時間を短くする方法が必要です。

DBMを使用して、事前に計算された辞書を保存することをお勧めします。これは基本的に、コンテンツがディスクに保存され、アイテムを参照するときに検索される辞書です。詳細については、 http：//docs.python.org/library/anydbm.htmlを参照してください。唯一の欠点は、値が文字列でなければならないことです。そのため、たとえば、上位5つのエントリのカンマ区切りのリストを保存し、ルックアップ時に分割する必要があります。

DBをロードする必要がないため、これはpickleよりもはるかに速い開始時間を持ちます。また、sqliteを使用するよりもはるかに簡単です。

于 2012-05-31T13:53:51.817 に答える