Какой самый простой способ сохранить полнотекстовый индекс для поддержки поиска неполных слов? - PullRequest
Новая
       27

Какой самый простой способ сохранить полнотекстовый индекс для поддержки поиска неполных слов?

2 голосов
/ 18 ноября 2011

Каков самый простой способ хранения (большого) полнотекстового индекса, который поддерживает поиск неполных слов? Например, поиск индекса для colo должен вернуть Колорадо (среди прочего). Для контекста я индексирую около 60 000 географических объектов (страны, регионы / штаты, зоны метро и города).

В моей первой попытке я проиндексировал все подстроки в слове, начиная с первого символа длиной от двух символов до полного слова. Например, для слова «Колорадо» я создал следующие записи индекса: 

co
col
colo
color
colora
colorad
colorado

Но это привело к 160 000 записей индекса. Я пытаюсь свести это к чему-то более разумному, сохраняя возможность сопоставления по неполным словам и не допуская увеличения количества записей в индексе. Какие оптимизации следует рассмотреть, чтобы уменьшить индекс?

Ответы [ 2 ]

3 голосов
/ 29 ноября 2012

Я рекомендую использовать компактную версию Trie, например, Radix Tree .Есть хорошая реализация здесь в python.

radix tree

Веб-служба

Вы можете настроить отдельный веб-сервер для предоставления этой службы поиска, например, используя Flask .

Пример кода

Некоторые примеры кодов для

  • загрузки предопределенных названий мест с использованием python-radix-tree и
  • завершают префикс до точки, где неоднозначностьзапускается и
  • находит все префиксные совпадения до 10 записей.

ниже: 

from radix_tree import RadixTree

locations = [
    "los angeles",
    "san diego",
    "san francisco",
    "san marino",
    "santa monica"
]

trie = RadixTree()
for loc in locations:
    trie.insert(loc, loc)

print trie.complete("s")
print trie.search_prefix('san', 10)

Результат примера кода 

san
['santa monica', 'san diego', 'san francisco', 'san marino']
0 голосов
/ 18 ноября 2011

Я думаю, что вы должны только разветвлять узел, если у него есть два дочерних элемента, например нет разветвления на 'colorad'.

Я думаю, что вы также должны иметь возможность хранить все это в одном файле, чтобы не платить 4 КБ накладных расходов за каждые несколько байтов, которые вы храните, и даже 60 000 объектов не будут очень большими, в среднем 30 байтов на строку дают вам ~ 1,8 МБ:)

...