, который datastructure или алгоритм, используемый для упорядочивания данных словаря для поиска последовательности?

Question

У меня есть словарь с около миллиона слов. Я должен разработать алгоритм для быстрого поиска последовательности символов.

Для примера. если пользовательские типы and приложение должно возвращать слова, имеющие такую ​​же последовательность, как random, sand, stand ... и т. д.

Существующее решение, которое у меня есть, - это поиск соответствующего регулярного выражения во всех существующих словах, которые неэффективны. Я открыт для реструктуризации существующей базы данных, кеширования словаря или работы на любом уровне, если требуется. Или есть ли готовые api в java?

Answer 1

Я бы попробовал использовать trie (Where do I find a standard Trie based map implementation in Java?). Использование в памяти индекса lucene может также соответствовать счету, в зависимости от ваших требований.

Answer 2

http://lucene.apache.org/core/

Посмотрите на это, это должно удовлетворить ваши требования.

final File INDEX_DIR = new File("index"); 
try{ 
    Class.forName("com.mysql.jdbc.Driver").newInstance(); 
    Connection conn = DriverManager.getConnection("jdbc:mysql://localhost/test", "root", "password"); 
    StandardAnalyzer analyzer = new StandardAnalyzer(); 
    IndexWriter writer = new IndexWriter(INDEX_DIR, analyzer, true); 
    System.out.println("Indexing to directory '" + INDEX_DIR + "'..."); 
    indexDocs(writer, conn); 
    writer.optimize(); 
    writer.close(); 
} catch (Exception e) { 
    e.printStackTrace(); 
} 

void indexDocs(IndexWriter writer, Connection conn) throws Exception { 
String sql = "select id, name, color from pet"; 
Statement stmt = conn.createStatement(); 
ResultSet rs = stmt.executeQuery(sql); 
while (rs.next()) { 
    Document d = new Document(); 
    d.add(new Field("id", rs.getString("id"), Field.Store.YES, Field.Index.NO)); 
    d.add(new Field("name", rs.getString("name"), Field.Store.NO, Field.Index.TOKENIZED)); 
    d.add(new Field("address", rs.getString("address"),Field.Store.NO, Field.Index.TOKENIZED)); 
    writer.addDocument(d); 
    } 
}