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

Question

我有一本大约有一百万字的字典。我必须设计算法来快速搜索字符序列。

例如。如果用户键入，则应用程序必须返回具有, , ... 等 and序列的单词。randomsandstand

我现有的解决方案是在所有现有单词中搜索匹配的正则表达式，这是无效的。如果需要，我愿意重组现有数据库、字典缓存或任何级别的工作或者在 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);  
  }  
}  

Answer 2

我会尝试使用 trie（在哪里可以找到 Java 中基于标准 Trie 的地图实现？）。根据您的要求，使用内存中的 lucene 索引也可能符合要求