bir sözlük harfi eksik kelimeleri ararken için verimli bir algoritma yazmam gerekiyor ve olası kelimelerin ayarlamak istiyorum.

Eğer th varsa örneğin,??e, bunlar, şunlar, onlar, orada tema geri verebilirim.vb.

Eğer herkes bazı veri yapıları önerebilirim eğer ya da kullanmam gereken algoritma merak ediyordum.

Teşekkürler!

EDİT: BİR Sükunet alanı-çok verimsiz ve çok yavaş olur. Başka fikri olan değişiklikler?

İKİ soru işaretleri olacak ve iki soru işareti oluşuyor, sırayla ortaya çıkar. GÜNCELLEME:

Şu anda tam bir eşleşme, 1 soru işareti, ve 2 soru işaretleri için 3 hash tabloları kullanıyorum. Sözlük ben verilen tüm olası kelimeleri karma. Eğer kelime KELİME var örneğin. KELİMESİ karma, ?ORD, W?RD, WO?D, KEL?, ??RD, W??D, WO??. sözlüğün içine. Sonra çarpışmalar birbirine bağlamak için bir bağlantı listesi kullanıyorum. Yani karma(W?RD) = hash(STR?NG) = 17. hashtab(17) WORD işaret eder ve KELİME bağlantılı bir listesini olduğundan bir dizeye işaret ediyor.

Tek kelime ortalama arama zamanı 2e-6. Daha iyi, tercihen 1e-9 sipariş yapmak için arıyorum.

Bu sorun bir daha bakmadım ama 3m girişleri için 0,5 saniye sürdü eklemeler ve 3m girişleri için 4 saniye arama aldı. EDİT:

Teşekkürler!

En iyisi her kelime bir çizgide nerede durduğunu düz bir dosya kullanın, Bu durumda inanıyorum. Buna uygun olan son derece optimize edilmiş ve muhtemelen herhangi bir veri yapısı yenecek olan bir düzenli ifade Arama, gücünü kullanabilirsiniz bu sorun için kendinizi hazırlamak.

Çözüm #1: Düzenli İfade Kullanarak

Bu sorun için Ruby kod çalışıyor:

def query(str, data)    
  r = Regexp.new("^#{str.gsub("?", ".")}$")
  idx = 0
  begin
    idx = data.index(r, idx)
    if idx
      yield data[idx, str.size]
      idx  = str.size   1
    end
  end while idx
end

start_time = Time.now
query("?r?te", File.read("wordlist.txt")) do |w|
  puts w
end
puts Time.now - start_time

8* *dosyası 45425 kelimeler (here indirilebilir) içerir. Sorgu için programın çıkış ?r?te:

brute
crate
Crete
grate
irate
prate
write
wrote
0.013689

Sadece 37 milisaniye her iki dosyanın tamamını okuyup, tüm eşleşmeleri bulmak için fırsat kollamaya başladılar. Ve bir Sükunet çok yavaş hatta çok iyi sorgu desenleri her türlü baskül:

????????????????e sorgu

counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681

?h?a?r?c?l? sorgu

theatricals
0.013608

Bu yeterince hızlı görünüyor.

Çözüm #2: Hazırlanan Verileri ile Düzenli

Eğer daha hızlı gitmek istiyorsan, eşit uzunlukta sözler içeren dizeler içine kelime listesi bölünmüş ve sadece doğru bir sorgu uzunluğuna göre arama yapabilirsiniz. Bu kod ile son 5 satırı değiştirin

def query_split(str, data)
  query(str, data[str.length]) do |w|
    yield w
  end
end

# prepare data    
data = Hash.new("")
File.read("wordlist.txt").each_line do |w|
  data[w.length-1]  = w
end

# use prepared data for query
start_time = Time.now
query_split("?r?te", data) do |w|
  puts w
end
puts Time.now - start_time

Veri yapısı bina yaklaşık 0.4 saniye sürer, ama şimdi tüm sorgular, yaklaşık 10 kat daha hızlı (bu uzunlukta kelime sayısına bağlı olarak)

• ?r?te 0.001112 sn
• ?h?a?r?c?l? 0.000852 sn
• ????????????????e 0.000169 sn

Çözüm #3: Büyük Karma Tablosu (Gereksinimleri Güncellendi)

Gereksinimleri değişti bu yana, kolayca önceden hesaplanmış sonuçlarını içeren tek bir büyük karma tablo kullanmak için fikrini daha da genişletebilirsiniz. Ama çarpışmalar etrafında çalışmak yerine kendinizi doğru şekilde uygulanması için bir karma tablo performansına güveniyor.

Burada sonuçları bir liste her olası sorgu haritalar nerede koca bir karma tablo, ben oluşturmak:

def create_big_hash(data)
  h = Hash.new do |h,k|
    h[k] = Array.new
  end    
  data.each_line do |l|
    w = l.strip
    # add all words with one ?
    w.length.times do |i|
      q = String.new(w)
      q[i] = "?"
      h[q].push w
    end
    # add all words with two ??
    (w.length-1).times do |i|
      q = String.new(w)      
      q[i, 2] = "??"
      h[q].push w
    end
  end
  h
end

# prepare data    
t = Time.new
h = create_big_hash(File.read("wordlist.txt"))
puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash"

# use prepared data for query
t = Time.new
h["?ood"].each do |w|
  puts w
end
puts (Time.new - t)

Çıktı

4.960255 sec preparing data
616745 entries in big hash
food
good
hood
mood
wood
2.0e-05

Sorgu performansı O(1), karma tablo içinde sadece bir arama. Zaman 2.0 e-05 muhtemelen zamanlayıcı hassas altındadır. Bunu 1000 kez çalıştırırken, 1.958 ortalama alıyorum e-6 sorgu başına saniye. Daha hızlı almak için, C geçiş ve bellek son derece verimli ve hızlı olan Google Sparse Hash kullanırdım.

Çözüm #4: Çok Ciddi

Çözüm yukarıdaki tüm çalışma ve birçok kullanım durumları için yeterince iyi olmalıdır. Eğer gerçekten ciddi bir ilişki ve ellerinde yedek bir sürü zaman sahip olmak istiyorsanız, iyi bir makale okudum:

• Tries for Approximate String Matching - Eğer iyi uygulandığı Takdirde, çalışır ve çok küçük bellek gereksinimi (sözlük kendisi P daha az yer) olabilir, ve çok hızlı.
• Agrep - A Fast Approximate Pattern-Matching Tool - Agrep yaklaşık dize eşleştirme için verimli ve esnek yeni bir algoritma dayanmaktadır.
• Google Scholar search for approximate string matching - gereğinden Daha fazla bilgi edinin bu konuda.