搜索最长的前缀

Question

我们假设它有一串字符串D。给定字符串Q，我想查找D中具有最长公用前缀Q的字符串。

我不想要一个复杂的数据结构，但它仍然应该比单纯的线性扫描更快。

是否有解决方案，以巧妙的方式排序D，只做一个二进制搜索？

谢谢！

编辑

澄清：当然，如果只进行一次，单次扫描是比排序更快。然而，我需要在固定的D上做很多这样的查找，所以这就是我寻找预计算数据结构的原因。

Answer 1

我在Java中一起实现了一个实现（因为我不知道如何打印或javascript）。这个方法虽然可以翻译，所以我希望这可能会有所帮助。

这是我的思维过程：

d是恒定的，所以我们要找到一种方法，找到具有共同的前缀的所有单词。因此，为此我执行：

• 一种树状结构，它根据字符的字符串对字符串进行索引。意字符串artur将被存储在a - >r - >t - >u等
• 这使索引d在时间O（n），其中n是串的长度的复杂性。
• 这使得搜索词共享一个共同的前缀为O（n），其中n是我们正在寻找的

该方法的前缀长度有一些限制，这样我可以更快的测试： *只允许小写字母 *将字符串存储在中间以避免在查找前缀时遍历树。

所以，我的代码，我有这些测试，还增加了一些时间，看看会发生什么：

public class CommonPrefixTree { 

    public static void main(String[] args) { 
     Node treeRoot = new Node(); 

     index("Artur", treeRoot); 
     index("ArturTestMe", treeRoot); 
     index("Blop", treeRoot); 
     index("Muha", treeRoot); 
     index("ArtIsCool", treeRoot); 

     List<String> strings = new ArrayList<>(); 

     char[] chars = "abcdefghijklmnopqrstuvwxyz".toCharArray(); 
     Random r = new Random(); 
     for(int i = 0; i < 500000; i++) { 
      StringBuffer b = new StringBuffer(); 
      for(int j = 0; j < 20 ; j++) { 
       b.append(chars[r.nextInt(chars.length)]); 
      } 
      strings.add(b.toString()); 
      index(b.toString(), treeRoot); 
     } 

     strings.add("art"); 
     strings.add("a"); 
     strings.add("artu"); 
     strings.add("arturt"); 
     strings.add("b"); 

     System.out.println(" ----- Tree search -----"); 
     find("art", treeRoot); 
     find("a", treeRoot); 
     find("artu", treeRoot); 
     find("arturT", treeRoot); 
     find("b", treeRoot); 

     // The analog test for searching in a list 

     System.out.println(" ----- List search -----"); 
     findInList("art", strings); 
     findInList("a", strings); 
     findInList("artu", strings); 
     findInList("arturt", strings); 
     findInList("b", strings); 

    } 

    static class Node { 

     Node[] choices = new Node[26]; 
     Set<String> words = new HashSet(); 

     void add(String word) { 
      words.add(word); 
     } 

     boolean contains(String word) { 
      return words.contains(word); 
     } 

    } 

    static List<String> findInList(String prefix, List<String> options) { 
     List<String> res = new ArrayList<>(); 
     long start = System.currentTimeMillis(); 
     for(String s : options) { 
      if(s.startsWith(prefix)) res.add(s); 
     } 

     System.out.println("Search took: " + (System.currentTimeMillis() - start)); 
     return res; 
    } 

    static void index(final String toIndex, final Node root) { 
     Node tmp = root; 
     // indexing takes O(n) 
     for(char c : toIndex.toLowerCase().toCharArray()) { 
      int val = (int) (c - 'a'); 
      tmp.add(toIndex); 
      if(tmp.choices[val] == null) { 
       tmp.choices[val] = new Node(); 
       tmp = tmp.choices[val]; 
      } else { 
       tmp = tmp.choices[val]; 
       if(tmp.contains(toIndex)) return; // stop, we have seen the word before 
      } 
     } 
    } 

    static Set<String> find(String prefix, final Node root) { 

     long start = System.currentTimeMillis(); 

     Node tmp = root; 
     // step down the tree to all common prefixes, O(n) where prefix defines n 
     for(char c : prefix.toLowerCase().toCharArray()) { 
      int val = (int) (c - 'a'); 
      if(tmp.choices[val] == null) { 
       return Collections.emptySet(); 
      } 
      else tmp = tmp.choices[val]; 
     } 

     System.out.println("Search took: " + (System.currentTimeMillis() - start)); 
     return tmp.words; 
    } 
} 

结果树和原始列表搜索

那么这将导致这些对于5个搜索100，10000和500k的字符串的定时：

----- Tree search ----- 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
----- List search ----- 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 

----- Tree search ----- 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
----- List search ----- 
Search took: 2 
Search took: 2 
Search took: 2 
Search took: 2 
Search took: 2 

----- Tree search ----- 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
Search took: 0 
----- List search ----- 
Search took: 43 
Search took: 27 
Search took: 66 
Search took: 25 
Search took: 24 

的主要问题有，这是创建树（这可能只是我的哈克实施一棵树或我浪费内存做它的方式）。所以还有改进的空间。树的创建确实需要很长时间。

该实验表明，对于这个常见前缀的查找使用树的时间消耗是稳定的。

观光虽然考虑可能是：

• 用于数据结构稀疏数组。
• 不存储实际的字符串，而是遍历树找到所有常用前缀

希望帮助 - 好玩的小运动。让我知道如果我塞进它完全:​​)

上排序输入的二进制搜索

我也注意到你问一个不复杂的数据结构，所以我尝试了以下内容：

• 对字符串的输入列表进行排序
• 二进制搜索匹配我们寻找的前缀的第一个索引
• 收集左右前缀

这将导致该代码（再次，抱歉，这是Java，但它应该是翻译很容易:)

static Set<String> getCommonPrefix(final String prefix, final List<String> input) { 

     long start = System.currentTimeMillis(); 

     int index = Collections.binarySearch(input, prefix, new Comparator<String>() { 
      @Override 
      public int compare(String o1, String o2) { 
       // o2 being the prefix 
       if(o1.startsWith(o2)) return 0; 
       return o1.compareTo(o2); 
      } 
     }); 

     if(index < 0) { 
      return Collections.emptySet(); 
     } 

     Set<String> res = new HashSet<>(); 
     res.add(input.get(index)); 

     boolean keepSearching = true; 
     int tmp = index - 1; 
     while(keepSearching && tmp > 0) { 
      if(input.get(tmp).startsWith(prefix)) { 
       res.add(input.get(tmp)); 
      } else { 
       keepSearching = false; 
      } 
      tmp--; 
     } 

     keepSearching = true; 
     tmp = index + 1; 
     while(keepSearching && tmp < input.size()) { 
      if(input.get(tmp).startsWith(prefix)) { 
       res.add(input.get(tmp)); 
      } else { 
       keepSearching = false; 
      } 
      tmp++; 
     } 

     System.out.println("Search took: " + (System.currentTimeMillis() - start)); 

     return res; 
    } 

这其中有一个有趣的现象。搜索将采取O(log n)，其中n是数组的输入大小。然后集合是线性的k其中k是通用前缀的数量。

有趣的是，只要前缀相当大，这种方法非常快（与树实现相比），但是一旦你寻找非常少的前缀，这会变得有点慢，要检索的字符串相当大。详细的时序为（500万个随机字符串）：

Search for 'art' took: 1 
Found strings: 309 
Search for 'artur2' took: 0 
Found strings: 1 
Search for 'asd' took: 0 
Found strings: 265 
Search for 'nnb' took: 1 
Found strings: 276 
Search for 'asda' took: 0 
Found strings: 10 
Search for 'c' took: 63 
Found strings: 192331 

我想，从一个Java的脚本点，如果你有一个内置的二进制搜索，最后的方法可能是最简单，最直接的选择就是构建和维护一棵树，这对我来说有点更重要（对我来说）花了很多时间来对字符串进行索引。

Answer 2

在D创建基于字符的树：

每个node包含character和儿童node s的名单。

例如，如果D是

a 
ab 
ac 
ace 
d 

然后

• 有2个顶级节点a和d
• d一直没有孩子
• a有2个孩子 - b和c
• b没有孩子
• c有1个小孩 - （！并添加到树）e
• e有没有孩子

查找基本上走的节点，直到没有匹配的儿童。

例如，假设Q=af。有一个包含Q[0]=a的顶级节点，但它没有Q[1]=f的子节点，所以最长的前缀是a。 a节点的所有子节点代表D中的字符串，其最长公共前缀为Q，具体为a,ab,ac,ace。

查找和添加操作在字符串长度中都是线性的，因此创建结构需要O(sum(len(x) for x in D))时间并且查找是O(len(Q))。