字为单位的超级字符串搜索指定字符串 [英] Word-wise super string search for given string

问题描述

对于任何输入字符串，我们需要找到超级字符串是任意顺序的词匹配。即，在输入字符串中的所有单词都发生在输出串中的任何顺序。 例如给定数据集： 字符串搜索 Java字符串搜索 手册C字符串搜索等于 java的搜索code C的java code搜索 ......

For any input string, we need to find super string by word match in any order. i.e. all words in the input string has to occur in any order in output string. e.g. given data set: "string search" "java string search" "manual c string search equals" "java search code" "c java code search" ...

输入java的搜索 输出： 1）的java字符串搜索 2）的Java搜索code 3）C的java code搜索

input: "java search" output: 1) "java string search" 2) "java search code" 3) "c java code search"

输入：搜索C 输出： 1）手册C字符串搜索等于 2）C的java code搜索

input: "search c" output: 1) "manual c string search equals" 2) "c java code search"

这可与文字匹配的单词一个很琐碎的方式来完成。在这里，主要是我要寻找一个高效的算法中。

This can be done in a very trivial way with word by word matching. Here mainly I am looking for an efficient algo.

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

Input: A few billion records in given data set (mostly 1 to 10 words length string). I need to find super string for millions of strings. Note: words are extended dictionary ones.

推荐答案

preprocess您的输入（如果可能的话），和索引出现在数据集中的话。生成从每个字的映射到一组可能的输出字符串。例如，对于数据集

Preprocess your input (if possible), and index the words that appear in the dataset. Generate a mapping from each word to a set of possible output strings. For example, with the dataset

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.

这篇关于字为单位的超级字符串搜索指定字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！