Поиск префикса стиля автозаполнения

Да, мы можем использовать попытку. Наиболее частыми именами для узла дерева являются либо (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)

Не имея никакого представления о настройке, я бы начал с предположения, что у меня есть список имен и их частот, затем создаю словарь, отображающий префиксы в набор имен с этим префиксом, а затем превращаю каждый набор в список только 5 лучших имен w.r.t. частота.

Используя список только имен мальчиков, полученный из здесь создан текстовый файл , где каждая строка целочисленная частота появления, несколько пробелов, затем имя вроде этого:

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
>>> 

Вы можете существенно расширить реализацию trie, чтобы хранить дочерние элементы в порядке популярности, а не в алфавитном порядке, при этом вам также придется хранить популярность в каждом узле trie.

Вот идея, как это сделать:

Создайте строку trie и сохраните целое число с каждым узлом в дереве. Этот узел указывает количество имен, которые используют этот узел. Таким образом, вы будете увеличивать все узлы имени, когда это имя вставляется в дерево.

Затем вы можете определить лучшие имена, жадно выбрав имена с самыми высокими значениями.

Формально это было бы то же самое, что и любой алгоритм построения дерева строк, но с добавленным шагом увеличения целых чисел.

Если вам нужен быстрый поиск, единственным реальным решением будет предварительное вычисление ответов для любого заданного префикса. Это нормально, если данные не изменяются, но вам нужен способ сократить время загрузки.

Я бы предложил использовать DBM для хранения предварительно вычисленного словаря. По сути, это словарь, содержимое которого хранится на диске и просматривается по мере того, как вы ссылаетесь на элементы. Подробнее см. http://docs.python.org/library/anydbm.html. Единственным недостатком является то, что значения должны быть строками, поэтому вам нужно будет хранить список, разделенный запятыми, скажем, из 5 первых записей, и разбивать его при поиске.

Это будет иметь гораздо более быстрое время запуска, чем рассол, так как БД не нужно загружать. Это также намного проще, чем использование sqlite.