搜索字符串集中的字符串排列

Question

这是一种尴尬的标题;我不确定如何总结这一点。我知道我该如何做到这一点，但我不确定如何有效地做到这一点。这是我的问题：

我有一个字符串作为输入。比方说：

富巴

而且我有一个非常大的组字符串（数万）的。比方说：

富，巴兹，酒吧，等等，富吧，富巴兹

我需要输入匹配的字符串集合。在这种情况下，“foo”，“bar”和“foo bar”被视为匹配。因此，我需要以某种方式搜索输入的所有排列（可能长于2个单词），或者以某种方式检测用户是否打算将其（或其一部分）放在引号中。或者做一些我没有想到的事情。

是否有某种数据结构或算法可用于此？我应该如何去做，或者我不应该处理这个用例？

编辑：上面有一个错字，扭曲了这个问题;在上面的例子中，“foo baz”也是匹配的。对于那个很抱歉。我基本上想要将输入单词的任何排列匹配到字典。因此，“abc xyz”的输入将匹配“123 abc”或“abc xyz”或“xyz 123”，但不匹配“abcxyz”。

Answer 1

我建议使用的字典。使用字符串作为键和字符串列表作为值。对要搜索的字符串进行标记，并将整个字符串添加到您的字典中，以便为每个标记添加一次。 （Youn可以使用split方法来标记字符串，使用空格作为分隔符。）之后，无论何时您需要查找，都会标记搜索字符串并查找字典中的每个标记。

因此，如果您已经添加下列字符串：FOO，巴兹，酒吧，等等，富吧，富巴兹

你的字典里条目：

富：FOO，FOO酒吧，富巴兹 巴兹：巴兹，富巴兹 酒吧：酒吧，酒吧FOO等等 ：等等

如果您再搜索“富巴”，

你的输出是下FOO存储和酒吧像条目的工会所以： “富巴”：= FOO，酒吧

富：FOO，FOO酒吧，富巴兹 工会 酒吧：酒吧，FOO酒吧

捐赠：FOO，FOO酒吧，富巴兹，酒吧

编辑：我刚刚注意到，你只需要完整或部分匹配，即foo巴兹是不可接受的。简单的解决方案是后处理结果 - 将搜索字符串和目标字符串的长度限制为较短字符串的长度，然后将截短字符串与未修改字符串进行比较。只接受那些相同的东西。

编辑：所以事实证明，foo baz确实是一场比赛。忽略上述段落（第一次编辑）。 见（C＃）代码如下：

class DictionarySearch 
{ 
    private Dictionary<string, List<string>> dict; 

    public DictionarySearch() 
    { 
     dict = new Dictionary<string, List<string>>(); 
    } 

    /// <summary> 
    /// Add a string e.g. foo bar to the dictionary 
    /// </summary> 
    /// <param name="s">string to be added</param> 
    public void addString(string s) 
    { 
     //tokenize string 
     string[] words = s.Split(new char[] { ' ' }); 

     //add each token to the dictionary as a key with the matching value being s 
     foreach (string w in words) 
     { 
      if (dict.ContainsKey(w)) 
      { 
       dict[w].Add(s); 
      } 
      else 
      { 
       dict.Add(w, new List<string>()); 
       dict[w].Add(s); 
      } 
     } 
    } 
    /// <summary> 
    /// Find all strings which match at least one token 
    /// </summary> 
    /// <param name="s">string of tokens (words) to be matched</param> 
    /// <returns>List of strings matching at least one word</returns> 
    public IList<string> getMatches(string s) 
    { 
     //split search string into words 
     string[] words = s.Split(new char[] { ' ' }); 
     List<string> output = new List<string>(); 

     //retrieve from dictionary list of strings matching each word. 
     foreach (string w in words) 
     { 
      if (dict.ContainsKey(w)) 
      { 
       output.AddRange(dict[w]); 
      } 
      else 
      { 
       continue; 
      } 
     } 

     return output; 
    } 
} 

鉴于与每串Q字和n的唯一字，并用升字的搜索串m串的辞典的时间复杂性是如下：

填充数据结构：O（q m T [dictionary-insert]）。需要对每个单词执行插入操作

查找字符串：O（l * T [dictionary-find]）。搜索字符串中的每个单词的字典查找。

实际成本取决于您的字典实施。基于哈希表的字典会导致插入和查找的O（1）成本。基于二叉树的字典会导致插入和查找的O（lg n）成本。

Answer 2

你需要的是Lucene

Answer 3

此代码有效。不知道这是否足够有效的为您：

String[] dict = "foo bar".split(" "); 

    String[] array = new String[] { "foo", "baz", "bar", "blah", "foo bar", 
      "foo baz" }; 

    loop: for (String s : array) { 
     String[] a = s.split(" "); 

     for (String sample : dict) 
      for (String s1 : a) 
       if (sample.equals(s1)) { 
        System.out.println(s); 
        continue loop; 
       } 
    } 

Answer 4

（当你说“高效”，你可能需要更明确的空间和时间方面让我们假设你的意思是时间效率（假设你提到了排列））。

计算的答案为

String[] findStringsContaining(List<String> strings, String[] words) 

的任务可以假定它是纯粹的功能和无副作用中的中间阶段，并且，其结果加入分区和越区切换到执行的并行线程，作为最后一步。即你可以分割单词和/或字符串列表。

这是map-reduce作品（和你的情况下，其不相关的，它的一切发生在同一台机器上。）

你映射（分配给每个词的线程）如何：

boolean [] stringContainsWord (List<String> strings, String word); 

该方法将并行执行。

然后，布尔数组对于给定单词匹配的每个索引（List）都有一个true。

和你的减速（运行的所有地图制作完成后）：

List<String> getMatchingList(List<String>, List<boolean[]> mapperResults); 

暂且不论开销线程并承担映射器线程数量可以忽略不计的成本为输入字的合理数量，这将给你是一个O（n）（对于mapper）+ O（m）（用于reducer）的时间过程，其中n是你的字符串列表中的项目数量，m是你输入中的单词数量。

您可以进一步并行化任务，方法是对每个字词分割字符串列表并运行p个线程，并让每个线程搜索字符串列表的子集，以便输入List到您的映射器1/p整体列表中的元素。

-

，你可能要考虑，特别是如果字符串列表是巨大的，而另一种方法，内容的langauge（如英语），是优化鉴于大多数语言有一小部分词组构成了该语言的大部分句子。例如，如果您的列表中有200万个英语句子，则可能是独特词语的列表要小很多个数量级（例如几百个）。

在这种情况下，您可以拥有单词 - >句子的地图，并且可以将测试任何给定单词的匹配句子的过程简化为地图中的查找。

（请注意，您仍然可以与此相结合的初步做法。）

Answer 5

从ejspencer的想法，我把这个一起

// Build the dictionary/data structure 
// O([average split length]*n) 
public static Dictionary<String,List<int>> BuildDictionary(String[] data) 
{ 
    String[] temp; 
    Dictionary<String,List<int>> dict = new Dictionary<String,List<int>>(); 
    for(int i = 0; i < data.length; i++) 
    { 
     temp = data[i].split(" "); 
     for(int j = 0; j < temp.length; j ++) 
     { 
      if(dict.get(temp[j]) == null) 
       dict.put(temp[j],new List<int>()); 

      dict.get(temp[j]).add(i); 
     } 
    } 

    return dict; 
} 

// find all the matches 
// O([average number of matches per key]*[input split length]) 
public static List<int> FindMatches(String input, Dictionary<String,List<int> dict) 
{ 
    String[] temp = input.split(" "); 
    List<int> ret = new List<int>(); 

    for(int i = 0; i < temp.length; i++) 
    { 
     if(dict.get(temp[i]) == null) 
      continue; // no match 

     // read the match into the return list, ignore copies 
     List<int> match = dict.get(temp[i]); 
     for(int j = 0; j < match.count(); j++) 
      if(!ret.contains(match.get(i)) 
       ret.add(match.get(i)); 
    } 

    return ret; 
} 

它可能不会编译正确了，但我想你”不管怎么样，它们都必须要和futz合作，这给了你一个快速访问和简单代码的好主意（没有进攻alphazero）。

此搜索区分大小写，但您可以随意使用toUpper或toLower来更改它。

Answer 6

你的字典有多大？你可以将你的字典转换为trie。人们已经发布了如何将字典转换为字典的内容。一旦你这样做，查找简单而快速。

此外，一个简单的解决方案可能是将搜索字符串分解为单独的单词，并在您的单词中搜索其中的每个单词，以确保重复单词不被考虑两次。

Answer 7

对于大型输入字符串和带有多个单词短语的字典，请考虑使用Rabin-Karp或Aho-Corasick算法。

（链接到拉宾 - 卡普 - http://en.wikipedia.org/wiki/Rabin -Karp_string_search_algorithm - 由于某种原因，我无法得到它的超链接高于参考）