1

对于任何输入字符串，我们需要以任意顺序逐字匹配查找超级字符串。即输入字符串中的所有单词必须以任何顺序出现在输出字符串中。例如给定数据集：“字符串搜索”“java 字符串搜索”“手动 c 字符串搜索等于”“java 搜索代码”“c java 代码搜索”...

输入：“java 搜索” 输出：1）“java 字符串搜索”2）“java 搜索代码”3）“c java 代码搜索”

输入：“搜索 c” 输出：1）“手动 c 字符串搜索等于”2）“c java 代码搜索”

这可以通过逐字匹配以非常简单的方式完成。这里主要是我在寻找一种有效的算法。

输入：给定数据集中的数十亿条记录（主要是 1 到 10 个字长的字符串）。我需要为数百万个字符串找到超级字符串。注意：单词是扩展字典的单词。

4

2 回答 2

1

预处理您的输入（如果可能），并索引出现在数据集中的单词。生成从每个单词到一组可能的输出字符串的映射。例如，使用数据集

0 string search
1 java string search
2 manual c string search equals
3 java search code
4 c java code search

我们得到

c {2,4}
code {3,4}
equals {2}
java {1,3,4}
...

Then, searching for the matches for a given input is as simple as intersecting the sets corresponding to the input word:

input: "java c"
output: {1,3,4} intersect {2,4} = {4}

If you store the sets just as sorted lists, intersection can be done in linear time (linear in the total length of the input sets) by scanning across the lists in parallel.

于 2013-03-30T06:09:46.217 回答
0

你基本上需要找到两组词的交集，input_words和data_words。如果交集等于 input_words，则您有匹配项。

以下是设置交集的有效算法：高效列表交集算法

我想到并在 O(n*m) [n = size input, m = size data] 中完成的算法是。

Python：

match = True
for word in input.split():
  if word in data_words.split(): # linear search comparing word to each word
    continue
  else:
    match = False
    break

排序列表上的搜索会更快，哈希查找会更多。这些在上面的链接中有详细说明。

于 2013-03-30T05:57:40.477 回答