處理在海量個(gè)字符串中找到某個(gè)字符串的方法
今天收到intel面試，問(wèn)我一個(gè)問(wèn)題，如何在一萬(wàn)個(gè)字符串中找到某個(gè)相關(guān)的字符串？當(dāng)時(shí)感覺(jué)打得不好，回頭自己又想了想，現(xiàn)寫(xiě)下感想。
方法1：最笨的方法，一個(gè)一個(gè)的遍歷
方法2：采用劃分子集的方法，首先以第1個(gè)字符進(jìn)行劃分，將a到z開(kāi)頭的字符串劃分到不同的子集中，然后比較，接著，再到相應(yīng)子集中進(jìn)行劃分，在比 較，一直到找到為止，這個(gè)方法相較于方法1是：1，相對(duì)于每次比較的字串而言，所有首字母不相同的不再進(jìn)行比較，比方說(shuō)happy，肯定去以h為首字母的 集合中進(jìn)行比較，然后對(duì)于子串a(chǎn)ppy，只要到所有子串以a為首字母的集合中進(jìn)行比較，如此下去，時(shí)間花費(fèi)主要在于劃分子集上，而劃分子集的次數(shù)又跟 happy的長(zhǎng)度有關(guān)系，所以只需劃分5次即可，所以時(shí)間復(fù)雜度是O(mn)，m是要尋找字符串的長(zhǎng)度，n是原始字符串集合大小。
方法3:采用正則表達(dá)式匹配，比如還是happy，假如將原始集合中的所有字符串和正則表達(dá)式pattern = ^h[A-Za-z]+y$進(jìn)行匹配，接著在對(duì)app這個(gè)子串和子集合中進(jìn)行正則表達(dá)式匹，pattern=^a[A-Za-z]+p$,最后對(duì)p進(jìn)行匹配即可，時(shí)間復(fù)雜度O(mn)
方法4：采用Hadoop海量數(shù)據(jù)處理，將海量字符串分到不同的map任務(wù)中，每個(gè)任務(wù)，進(jìn)行對(duì)字符串在相應(yīng)的node上進(jìn)行查找，接著對(duì)于所有的map的結(jié)果交給reduce任務(wù)分析，這僅僅是個(gè)方案，具體時(shí)間復(fù)雜度的話，看你有多少個(gè)map任務(wù)了。
方案5：采用trie樹(shù)，對(duì)這海量字符串構(gòu)建一顆trie樹(shù)，然后在trie樹(shù)中查找該字符串，trie樹(shù)的優(yōu)勢(shì)在于對(duì)于前綴一樣的字符串都可以在一次匹配查找中得到，時(shí)間復(fù)雜度在于構(gòu)建trie樹(shù)復(fù)雜度，和trie樹(shù)的高度。
方案6：可以采用編譯原理學(xué)到的自動(dòng)機(jī)，最近再看編譯原理突然想到，不過(guò)對(duì)于海量數(shù)據(jù)，具體情況怎么樣，還得我繼續(xù)探索~~
喜歡 
頂
難過(guò)
囧
圍觀
無(wú)聊
