Этот пример подходит для небольших списков URL, но не очень хорошо масштабируется.
def longest_prefix_match(search, urllist):
matches = [url for url in urllist if url.startswith(search)]
if matches:
return max(matches, key=len)
else:
raise Exception("Not found")
Реализация, использующая модуль trie .
import trie
def longest_prefix_match(prefix_trie, search):
# There may well be a more elegant way to do this without using
# "hidden" method _getnode.
try:
return list(node.value for node in prefix_trie._getnode(search).walk())
except KeyError:
return list()
url_list = [
'http://www.google.com/mail',
'http://www.google.com/document',
'http://www.facebook.com',
]
url_trie = trie.Trie()
for url in url_list:
url_trie[url] = url
searches = ("http", "http://www.go", "http://www.fa", "http://fail")
for search in searches:
print "'%s' ->" % search, longest_prefix_match(url_trie, search)
Результат:
'http' -> ['http://www.facebook.com', 'http://www.google.com/document', 'http://www.google.com/mail']
'http://www.go' -> ['http://www.google.com/document', 'http://www.google.com/mail']
'http://www.fa' -> ['http://www.facebook.com']
'http://fail' -> []
или используя PyTrie , который дает тот же результат, но списки упорядочены по-разному.
from pytrie import StringTrie
url_list = [
'http://www.google.com/mail',
'http://www.google.com/document',
'http://www.facebook.com',
]
url_trie = StringTrie()
for url in url_list:
url_trie[url] = url
searches = ("http", "http://www.go", "http://www.fa", "http://fail")
for search in searches:
print "'%s' ->" % search, url_trie.values(prefix=search)
Я начинаю думать, что основополагающее дерево / дерево Патриции будет лучше с точки зрения использования памяти. Вот как будет выглядеть основное дерево:
Принимая во внимание, что дерево больше похоже на:
