Hızlı ön ek arama ile dizelerin (yaklaşık 100.000) salt okunur bir listesi için en verimli veri yapısı

Question

Bir dosyadan dizelerin bir listesini okumak, bunları bir veri yapısına kaydetmek ve sonra da bu dizeleri öneklere göre arayın. Dizelerin listesi, yalnızca belirli bir dilde yazılmış sözcüklerin listesidir. Örneğin, arama fonksiyonu bir parametre olarak "stup" alırsa, ["stupid", "aptallık", "stupor" ...] döndürmelidir. O (log (n) * m) zamanında bunu yapmalıdır, burada n veri yapısının büyüklüğüdür ve m, sonuçların sayısıdır ve olabildiğince hızlı olmalıdır. Bellek tüketimi şu anda büyük bir sorun değil. Bunu pythonda yazıyorum, python sarmalayıcıları ile c içinde uygulanan uygun bir veri yapısına (tercihen) işaret ederseniz, bu harika olurdu.

Answer 1

Bir parça istiyorsanız.

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

Ben Scrabble ve Boggle programlarında bunları kullandım. Tanımladığınız kullanım durumu için mükemmeller (hızlı önek araması).

Python'da bir tray oluşturmak için bazı örnek kodlar. Bu birkaç ay önce birlikte çektiğim bir Boggle programından. Kalan okuyucuya bir egzersiz olarak bırakılmıştır. Ancak, önek denetimi için temel olarak kök düğümde (words değişkeni) başlayan bir yönteme gereksinim duyarsınız, ardışık alt düğümler için önekin harflerini izler ve böyle bir yol bulunursa ve aksi halde yanlışsa True değerini döndürür.

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

Answer 2

A trie (or prefix tree) sağ biçilmiş kaftan geliyor. O (m) 'deki bir m uzunluğunda önek dizesi üzerinde arama yapabilir.

Answer 3

dize dizisi. içinden

sonra ikili arama ilk maçı sonra burada da sonraki tüm maçları için içinden birer

(i başlangıçta bağladı listesini birinci adıma aramak ... ama tabii bu rastgele yok erişim nedenle bu (ı downvoted neden muhtemelen açıklar) 'bs' oldu Benim ikili arama algoritması hala gitmek için en hızlı yoldur olsa tries ait

Answer 4

Bazı Python uygulamaları:.

• http://jtauber.com/2005/02/trie.py
• http://www.koders.com/python/fid7B6BC1651A9E8BBA547552FE3F039479A4DECC45.aspx
• http://filoxus.blogspot.com/2007/11/trie-in-python.html