針對給定字符串的單詞超級字符串搜索

對於任何輸入字符串，我們需要按任意順序通過單詞匹配查找超級字符串。即輸入字符串中的所有字都必須以輸出字符串中的任何順序出現。例如給定數據集：「字符串搜索」的「java字符串搜索」「手冊C字符串搜索等於」「Java的搜索代碼」「C Java代碼搜索」 ...針對給定字符串的單詞超級字符串搜索

輸入：「java的搜索」輸出： 1）「Java字符串搜索」 2）「Java的搜索代碼」 3）「C Java代碼搜索」

輸入：「搜索C」輸出： 1）「手冊C字符串搜索等於「 2）」c java代碼搜索「

這可以通過逐字匹配以非常小的方式完成。這裏主要是我正在尋找一個高效的算法。

輸入：給定數據集中的幾十億條記錄（大多數是1到10個字長的字符串）。我需要爲數百萬個字符串找到超級字符串。注意：單詞是擴展字典的。

來源

2013-03-30 user2226441

你應該去正則表達式 – MeetM

正則表達式比較一個輸入字符串與所有data_set（這是數十億）是相當高的。現在我需要重新操作一百萬次（如果不是十億次）輸入字符串！ – user2226441

預處理您的輸入（如果可能的話），並索引出現在數據集中的單詞。從每個單詞生成映射到一組可能的輸出字符串。例如，與數據集

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} 
...

然後，搜索給定輸入比賽是交叉對應輸入字組那樣簡單：

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

如果您將集合存儲爲排序列表，則可以通過並行掃描列表以線性時間（輸入集合的總長度中的線性）完成交集。

來源

2013-03-30 06:09:46 nneonneo

你基本上需要找到兩組單詞input_words和data_words的交集。如果交叉點等於input_words，則表示匹配。

以下是交集有效的算法：Efficient list intersection algorithm

這使我的思想和在O（n * m個）完成的算法[N =尺寸輸入，M =大小數據]是。

的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-30 05:57:40

針對給定字符串的單詞超級字符串搜索

回答

相關問題