java - 使用哪种数据结构或算法来安排字典数据以进行序列搜索？

Question

我有一本字典，里面有将近一百万个单词。我必须设计用于快速搜索字符序列的算法。

例如。如果用户键入 and，应用程序必须返回具有类似 random,sand,stand 序列的单词 ...ETC。

我现有的解决方案是在所有现有的单词中搜索匹配的正则表达式，但效率不高。 如果需要，我愿意重组现有数据库、字典缓存或在任何级别工作或者是否有一些现成的 java api？

Answer 1

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);  
  }  
}