尋找更快速的方式來執行字符串搜索

我必須認識到一大羣網址（幾百萬行）屬於一個特定的類別或不。我有另一個具有子字符串的列表，如果該URL存在屬於該類別的話。例如，類別A.尋找更快速的方式來執行字符串搜索

要檢查的子字符串列表大約有10k個這樣的子字符串。我所做的只是在子字符串文件中一行一行地查找匹配項，並且如果找到該URL屬於類別A的話。我在測試中發現這很耗時。

我不是計算機科學專業的學生，所以沒有太多有關優化算法的知識。但是有沒有辦法讓這個更快？只是簡單的想法。編程語言不是一個大問題，但Java或Perl會更好。

要匹配的子字符串列表不會有太大變化。然而，我會收到不同的URL列表，所以每次得到它時都要運行它。瓶頸似乎是網址，因爲它們可能會變得很長。

來源

2011-04-13 sfactor

你可以使用一些信息檢索系統（即Lucene的 - 在Java中）索引的URL，然後搜索字符串，索引會費時，但可以爲每個「查詢」節省時間 - 無需遍歷整個列表。 – amit 2011-04-13 07:41:24

10K次，比如說1000萬是什麼，1000億？是的，不管語言如何，這都需要一些時間。如果A類中有某物，這是否意味着它們不能在其他類別中？如果是這樣，你可以從大列表中刪除所有分配給 – 2011-04-13 07:44:40

的大列表。子列表的列表是恆定的，沒有理由需要很長時間，查看我的答案列表的長度隻影響所用的大小內存的自動機，甚至可能會很小 – Asaf 2011-04-13 07:46:31

是的，我在java中使用了Aho-Corasick algorithm算法來解決你所提出的問題，它顯示了對天真實現（你在做什麼）x180的一致改進。網上有幾種實現可用，但我會調整它們以獲得更好的性能。請注意，解決方案的複雜性是由單詞的長度（在你的情況下的URL），而不是子字符串的數量。此外，它只需要一次平均匹配。

P.S-我們曾經在面試時將這個問題提供給人們，所以有很多方法可以解決這個問題。我提供的是我們在生產代碼中使用的那個，它（現在）擊敗所有其他解決方案。

編輯：寫錯算法名稱以前，固定......

來源

2011-04-13 07:44:50 Asaf

嘿謝謝，Aho-Corasick算法就像一個魅力。天真的實現獲得了約50倍的改進。只是多一個好奇心，KMP算法的性能如何？那會更快嗎？ :) – sfactor 2011-04-13 11:44:44

那，忘了KMP。這是我犯的一個錯誤（從錯誤的電子郵件中複製名稱）Aho-Corasick算法在輸入長度上是線性的，並且易於理解/實現，除非真的必要，否則我不會爲更多優化而煩惱。我做了什麼來加速它只是使用數組無處不在來表示節點之間的邊界（而不是地圖），並且原始算法返回匹配的位置。如果你揮動這個能力，你可以加快速度。 – Asaf 2011-04-13 11:57:00

您可以將子字符串壓縮成共享相同前綴的類。這應該使時間縮短很多。

如果您通過每次迭代將字符串移位1來查找匹配項，則可以使用更好的算法（與正則表達式一樣）提高您的速度。

來源

2011-04-13 07:42:35 bdares

如果您將所有子字符串放入一個正則表達式中，前綴優化會自動完成，至少通過合理優化的常規表達引擎。 – jmg 2011-04-13 07:45:55

我建議使用古老的Grep，而不是使用編程語言來完成此任務。它使用快速Boyer-Moore string searching algorithm，這應該足夠幾百萬行。

來源

2011-04-13 07:43:20 darioo

我不確定grep在這裏會有效率，如果不可能匹配，算法會跳躍到前面，如果你有10k個單詞，那麼grep可能會很難在前面跳過（或返回取決於優化），因爲會有很多通用的前綴（或後綴） – Asaf 2011-04-13 07:50:21

不同的方法當然可以優化這一點。關於你的背景，我會畫一個簡單的草圖。這假定子字符串列表不會經常更改。

從所有子字符串生成一個巨大的正則表達式。
編譯該正則表達式，請參閱。例如Java中的類Pattern。將refrence存儲到編譯的正則表達式。
使用相同的編譯正則表達式來匹配每個url。

來源

2011-04-13 07:44:25 jmg

我會打賭這將表現得很差，你有沒有試過用10k字符串做這樣的事情？子彈（1）將非常難以有效地取消，其餘的最終效果幾乎與天真實施一樣低效 – Asaf 2011-04-13 07:52:39

@Asaf：如果你的regexp引擎不好，或者如果你不預編譯正則表達式。但除此之外，它應該創建一個幾乎與KMP算法一樣好的自動機。我想給一個適用於沒有深厚計算機科學知識的方法。否則，KMP是顯而易見的解決方案。 – jmg 2011-04-13 08:04:30

@jmg，我同意KMP有點複雜，我的意思是Aho-Corasick並相應地解決了我的答案（我用KMP來解決不同的問題）。 Aho-Corasick有許多現成的[實現]（https://hkn.eecs.berkeley.edu/~dyoo/java/index.html），我感覺相對容易理解。此外，假設你會以某種方式從10k字符串中構建出「完美」的正則表達式，我認爲這是一個更難的算法問題，然後是原始問題，但我沒有看到該解決方案不會如何依賴（複雜性明智）的子字符串 – Asaf 2011-04-13 08:09:42

Perl是在正則表達式優化備用字符串的長列表（達到一定的整體編譯正則表達式的長度，它恢復到很好效率較低的機制）。你應該能夠構建一個正則表達式匹配某一類別，如：

$catAre = join('|', map quotemeta, @catAstrings); 
$catAre = qr/$catAre/;

來源

2011-04-13 07:48:02 ysth

對於實現共同字符串搜索算法看到答案https://stackoverflow.com/questions/5564610/fast-alernative-for-stringindexofstring-str Java庫。再加上並行化，你應該能夠相當快地解析數百萬個URL。這很容易做到;你應該嘗試一下，看看時間是否可以接受，然後再進一步觀察優化。

來源

2011-04-13 08:17:29 WhiteFang34

鏈接不工作 – therealprashant 2016-11-04 06:24:02

我第一次寫它的評論，但後來我意識到，我認爲這是作爲一個答案
你可以使用一些信息檢索系統（如Apache Lucene在Java中），並用它來索引網址，如文檔更合適。
然後，在編制索引之後 - 您可以迭代查詢，並搜索它們中的每一個，結果將是匹配的URL。
優先級：
*搜索不需要遍歷每個查詢的所有URl。
*如果您稍後將需要串/查詢的交集或並集 - 庫爲您提供了這一功能
缺點：
*索引將需要一段時間...
*您可能需要在RAM一些額外的空間/磁盤索引。

我認爲這是一個值得探討的方法，也許是時間消耗，而索引搜索價值的增益。

來源

2011-04-13 08:37:06 amit

我在Perl中做過這樣的事情，比較13K關鍵字〜清單針對從Twitter數據的輸入流找到任何匹配這些關鍵字的所有推特（以及關鍵字匹配每一個）。在粗略估計，代碼如下：

use Regexp::Assemble; 
my $ra = Regexp::Assemble->new; 
$ra->add(@keywords); 
my $regex = $ra->re; 

for my $tweet (@tweets) { 
    my @matches = $tweet =~ /$regex/g; 
    # do whatever with @matches... 
}

注意，這裏使用Regexp::Assemble打造的正則表達式，這不是核心的Perl發行版的一部分，所以你需要安裝，如果從CPAN如果你想修改此代碼。

如果您使用的是perl 5.10或更高版本，還有「智能匹配」運算符（~~），它可以在不需要任何附加模塊的情況下做類似的工作。

來源

2011-04-13 10:10:14

我目前正在研究這個問題。我得出這樣的結論：同時使樹

阿霍 - corasick會消耗更多的內存。如果沒有記憶的問題比它的好。但是看一下HAT Trie吧。它是散列和特里（樹）的組合。它將在某個級別生成一棵樹，其餘的字符將形成一個散列值，該散列值應該在哈希表中進行標記。

對不起更多的技術語言。但是如果您從URL列表中搜索特定的URL，我認爲HAT trie是更好的選擇。（我已經形成了HAT特里這將消耗12MB用於存儲URL的6lacks。）

來源

2012-08-21 05:55:48

即使你可以根據你的需要調整它。（法律記憶或更快的表現） – 2012-08-21 05:56:46

尋找更快速的方式來執行字符串搜索

回答

相關問題