Java'da basit bir önek dizini nasıl oluşturulur?

Question

Çok sayıda url var ve otomatik tamamlama uygulamak istiyorum. o seti boyutu ile doğrusal olduğu gibi naif bir yaklaşım karmaşıklığını sevmiyorum:

Şimdi bir Hash Set içinde, fonksiyon O" eserlerini "() içeriyor" olduğunu biliyoruz

for(String url: urls) if(url.startsWith(input) {doSomething();} 

(1) "ama" includePrefix() "yok. Lucene gibi büyük bir kütüphane kullanmadan ya da kendim kodlamadan basit bir yol var mı? Bunu yapmakta herhangi bir problemim olmazdı ama bu kadar basit bir problem için overkill görünüyor, bu yüzden var olan basit bir çözüm olup olmadığını bilmek istiyorum :-)

Bilgisayar bilimi sınıflarımdan, string fragmanlarından oluşan bir ağacı hatırlıyorum ama Nasıl çağrıldığını unuttum. Ben bir dize öneki olan tüm dizeleri döndüren yöntemleri çağırmak nasıl

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P.S. .:: Bu gibi çalıştı? Sanki b'nin bir öneki ise, b'ye göre nedir? Eğer bir Trie, bu amaçla tam olarak tasarlanmış bir veri yapısını kullanmak, verimli dizeleri önekleri bulmanız gerekiyorsa

Answer 1

:

Bir trie veya önek ağaç için kullanılan sıralı bir ağaç veri yapısı olduğunu Anahtarların genellikle dizeleri olduğu bir ilişkisel dizi saklar. Bir ikili arama ağacından farklı olarak, ağaçtaki hiçbir düğüm bu düğümle ilişkili anahtarı saklamaz; bunun yerine, ağacın içindeki konumu, ilişkili olduğu anahtarı tanımlar. Bir düğümün tüm soyundan o düğüm ile ilişkili dize ortak öneki var ve kök boş dize ile sampleimplementations ile

İki bağlantıları ilişkilidir.

Answer 2

Uzun zaman önce burada basit bir Trie uygulaması koyun:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

Ancak bu kompakt Trie değildir, bu nedenle kompakt bir biraz daha zordur oluşturarak, karakter başına bir düğüm oluşturur.

Answer 3

harika bir alternatif algo bir ternary search tree (verimli fazla bellek) burada

https://github.com/varunpant/TernaryTree/tree/master/TernaryTree java bir tray olduğu http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

verimli önekleri işleyebilir

Normal İfade uygulama java.util.regex.Pattern:

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

tüm önekleri test edebilirsiniz:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

Not: basitlik için önek dizeleri kaçtı değil. Regexp karakterleri [,], \, *,?, $, ^, (,), {,} Ve | \ ile önekli olmak zorunda.