高效实现相似字符串列表的搜索算法

Question

我不知道该怎么说。我将给你举一个例子。我有一个字符串列表，比如{"abc-1"，"abc-2"，"abc-3"，“abc-4"，"xyz-98"，"xyz-76"，"xyz-34"，"xyz-87”"foo-1a"，"foo-1b"，"foo-1c"}我希望你对这个问题有所了解。那么哪种算法最适合这种情况，在这种情况下，我们可以有大量的相似字符串。或者可能是我如何优化现有的算法以获得最佳性能？

Answer 1

优化它是为了什么？速度或大小。如果列表足够小，并且您只查找精确匹配，那么映射(HashMap / HashTable)就可以工作，但会占用大量空间。您可以使用Trie (前缀树)，它将在一些空间上进行空间，也允许前缀匹配，但比映射稍慢。

Answer 2

根据您的要求，您可以使用Prefix Tree (Trie)，对列表中的字符串使用Trie和布尔数组进行一些预处理。想法是这样的：

1. Create a pool of already existing strings from the List of Strings
   present and create a lookup based on Trie.
2. While creating the pool, split the string using "-" as delimiter.
3. The String part goes to searchin the Trie you have created. 
   If you find the search string in Trie, then search the Integer 
   part in the boolean array.
4. The boolean array is an array that would store true at the index 
   of number that is the post fix of the search string and is
   attached to the last node of the trie prefix.

简而言之，假设您想搜索字符串s= abc-2。

String[] inputStr = s.split("-");
if(searchTrieNode(inputStr[0])
    if(boolArr[inputStr[1]])
        return true;

编辑:如果数组的大小很大，我们也可以使用位串来存储模式串的数字信息，并将其附加到找到的最后一个trie节点的下一个指针。我们只需要设置nth位。例如，如果我们有abc-12，我们可以将第12位设置为1，并将其附加到abc trie结构的下一个指针。这样，我们也不会有任何内存浪费。在搜索时，我们只需要检索nth位并检查它是否设置为1。