Twitter熱門話題：結合不同的拼寫

Question

Twitter的熱門話題通常包含多個詞彙。但是，對於由條款往往有不同的方式拼寫，例如：

「混血王子」 /「混血王子」

要找到所有的更新提的一個熱門話題，你需要拼寫的所有方式。 Twitter的做到這一點：

Twitter's Trending Topics Admin http://i26.tinypic.com/hu4uw1.png

您對左邊和右邊的拼寫方式的不同主題名稱。你認爲這是手動還是自動完成的？是否有可能自動執行此操作？如果是的話：如何？

我希望你能幫助我。提前致謝！

Answer 1

我會嘗試基於失效鏈接的評論來回答我的問題（感謝您對本）：

---

你摘取語句由1至3個字從你的文檔數據庫。在這些extraced短語有下面的語句：

• 混血王子
• 混血王子
• 混血王子

對於每個短語，你帶所有的特殊字符和空格，使字符串小寫：

$ phrase ='混血王子'; $ phrase = preg_replace（'/ [^ a-z]/i'，''，$ phrase）; $ phrase = strtolower（$ phrase）; //結果是 「halfbloodprince」

當你做到了這一點，所有的3個階段（見上文）有一個共同的拼寫：

• 混血王子=> halfbloodprince
• 混血王子=> halfbloodprince
• 混血王子=> halfbloodprince

所以 「halfbloodprince」 是父短語。將兩者都插入數據庫，正常短語和父語句。

要顯示一個「熱門話題聯繫」 Twitter之類的，你做到以下幾點：

// first select the top 10 parent phrases 
$sql1 = "SELECT parentPhrase, COUNT(*) as cnt FROM phrases GROUP BY parentPhrase ORDER BY cnt DESC LIMIT 0, 10"; 
$sql2 = mysql_query($sql1); 
while ($sql3 = mysql_fetch_assoc($sql2)) { 
    $parentPhrase = $sql3['parentPhrase']; 
    $childPhrases = array(); // set up an array for the child phrases 
    $fifthPart = round($sql3['cnt']*0.2); 
    // now select all child phrases which make 20% of the parent phrase or more 
    $sql4 = "SELECT phrase FROM phrases WHERE parentPhrase = '".$sql3['parentPhrase']."' GROUP BY phrase HAVING COUNT(*) >= ".$fifthPart; 
    $sql5 = mysql_query($sql4); 
    while ($sql6 = mysql_fetch_assoc($sql5)) { 
     $childPhrases[] = $sql3['phrase']; 
    } 
    // now you have the parent phrase which is on the left side of the arrow in $parentPhrase 
    // and all child phrases which are on the right side of the arrow in $childPhrases 
} 

這是你想，斷開鏈路的什麼？這會工作嗎？

Answer 2

我記得當MJ去世時，twitter手動返回並且修復了主題以指向他的死訊。這些天要求計算機自動執行類似的操作將會非常困難，儘管它可以輕鬆完成。

Answer 3

你基本上想要的是找到similarity between two strings。

我認爲Soundex算法就是你要找的。它可以用來根據它們的聲音來比較字符串。或者作爲維基描述：

Soundex是一種用聲音索引名稱的語音算法，如英語發音。目標是將同音字編碼爲相同的表示形式，以便儘管在拼寫上存在細微差異，也可以匹配它們。

和：

使用這種算法[編輯：那就是，「評級」一個字母和三個數字的話]，無論是「羅伯特」和「魯珀特」返回相同的字符串「R163」而「魯賓」產生「R150」。 「Ashcraft」產生「A261」。

還有the Levenshtein distance。

祝你好運。

Answer 4

假設熱門話題是以計算方式生成的，那麼在Twitter上執行它的確切算法將很難猜測。它很可能是高度機密的，也是專利（專利算法聽起來很可怕）。

我覺得有理由相信他們會使用某種自然語言算法。根據具體情況，它們往往真的很沉重，無法進行計算，只會做你想要的一些擴展。

關於這個問題的一個明顯的有益讀是從維基：

• Natural language processing

好運。

Answer 5

有很多方法可以做到這一點。一個關於谷歌風格的直截了當的文章「你的意思是」檢查對於如何實現這一點的想法是一個很好的閱讀。谷歌研究總監皮特諾維格寫道。

http://norvig.com/spell-correct.html

Answer 6

「anderstornvig」中提到的萊文斯坦/編輯距離，這是一個好主意，但不是很合適，因爲某些排列比其他排列更顯著。問題似乎是，當我們確定哪些差異是「顯着的」，哪些是「微不足道的」時，我們正在使用大量特定領域的知識。例如，我們知道「混血王子」中的連字符非常重要，但「Firefox 3」中的數字非常重要。

由於這個原因，你可能會考慮定製一個像Levenshtein這樣的簡單度量。添加參數可讓您自定義哪些差異很重要，哪些不重要。

特別是，Levenshtein計算將一個字符串轉換爲另一個字符串所需的「編輯」數量（即插入，刪除和替換）。實際上，它將每個編輯權重相同。您可以編寫一個以不同方式加權某些編輯的實現。例如，將「 - 」改爲「」應該具有非常低的權重（表示不重要）。當數字是單獨的時，將「3」改變爲「2」應該具有非常高的權重（表示高度重要性）。

通過參數化計算，您可以創建一個不斷改進算法的途徑。構建一個初始配置並在一些測試數據上運行它。查找度量標準較弱的地方 - 例如，它將您認爲應該分隔的兩個詞彙合併在一起，然後修改參數化，直到您滿意爲止。

這樣，您可以使用您的領域特定知識來訓練您的算法。

Answer 7

最有可能他們有一些自動化系統，對合並建議可能的候選人，然後一個人做的最終選擇將它們結合起來。可能有一些它們會自動組合。

• 您對刪除空格和其他標點符號的建議是一個很好的建議。他們很可能將自動結合僅在標點符號或白色空間上不同的東西結合起來。
• 複數與單數：尋找這些差異很容易自動化，並且會產生可能的合併候選。
• 常見拼寫錯誤 - 有常見拼寫錯誤的數據庫。他們甚至可能依靠Google API來提供拼寫建議（我認爲他們揭示了這一點）。
• Soundex（或類似）是一個很好的用於尋找拼寫錯誤，但它需要首先通過上述兩個過濾器去（刪除空格，標點符號和複數），然後很可能需要一個人來撥打電話，如果他們是相同的。但是，如果您可以用相同或相似的soundex顯示集羣的圖形表示，那麼您真的可以輕鬆實現該部分。你可以在集羣開始出現和趨勢時自動發送通知（他們真的只關心趨勢主題，所以如果組合集羣不趨勢，他們可以等待檢查它）。

哪裏當真的有一個普通的暱稱時，你真的需要一個人來介入。像邁克爾傑克遜，MJ，邁克爾等等。或者MacDonalds，McD，Micky-D等等。然後用技術你有Visual Studio，VS2008，VS等或者StackOverflow，SO等等。然後C＃，C-Sharp， C＃.NET都是一樣的，但C和C++是不同的。

因此，這將需要一個組合。它可能依賴於基於以前的分析或其他來源的已知變化和組合的數據庫，但該數據庫將由編輯定期維護。