用於比較200k個字符串的數據結構

我有200,000個字符串。我需要找到那組中的類似字符串。我預計類似字符串的數量在集合中非常低。請幫助一個有效的數據結構。用於比較200k個字符串的數據結構

如果我正在查找完全匹配的字符串，我可以使用簡單的哈希值。但是，在我的情況下，「相似性」是自定義的：如果兩個字符串中的80％相同，則順序無關緊要。

我不想調用找到「相似性」〜（200k * 100k）次的函數。任何建議，像預處理字符串的技術，高效的數據結構都是受歡迎的。謝謝。

2012-12-27 syam

什麼是字符串的長度，平均與最大和最小？你可以製作一個直方圖，其中每個字符串都有一個直方圖排名，然後你可以簡單地按比例將它們組合在一起，在這種情況下，80％ –

「貓」與你的描述中的「abracatabra」具有100％的相似性，但是''abracatabra''有不到80％的'貓'。那是對的嗎？我的觀點是「相似性」不是很明確。 –

我想到的第一件事就是沒有比較。哈希函數如何？我在stackoverflow做了一點搜索，http://stackoverflow.com/questions/8848991/python-digest-hash-for-string-similarity – CppLearner

我知道只有兩個字符串之間的字符串長度差別爲< = 3時，距離比才有可能> = 0.85。這意味着，我們可以將長度差異爲< = 3的字符串進行分組。

這大大減少了每個組中的字符串數量。因此，我的數據集中整體比較的數量減少到略低於50％（200k * 100k）。此外，將數據集分成多個小集有助於進行並行處理，從而進一步減少整體運行時間。

減少百分比可能會隨着樣本數據集的變化而變化，即當所有字符串的長度差異爲< = 3時發生最壞情況。

[感謝因巴爾玫瑰刺激這種思想]

在我的情況下，直方圖看上去如下：

histogram

2013-01-07 08:54:30 syam

回答