用於比較詞彙相似度的數值散列

Question

是否有某種形式的散列算法可以爲相似的單詞生成相似的數值？我想會有一些誤報，但它似乎對搜索修剪很有用。

編輯：探測法整潔，可能會派上用場，但理想情況下，我想，其行爲是這樣的東西：abs(f('horse') - f('hoarse')) < abs(f('horse') - f('goat'))

Answer 1

什麼你正在談論被稱爲Locality-sensitive Hashing。它可以應用於不同類型的輸入（圖像，音樂，文本，空間位置，無論您需要什麼）。

不幸的是（儘管搜索）我找不到任何字符串LSH算法的實際實現。

Answer 2

Soundex算法生成對應於在輸入一個單詞的音素鑰匙串。 http://www.archives.gov/research/census/soundex.html

如果您只想比較字符串之間的相似性，請嘗試Levenstein距離。 http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

您可以隨時嘗試Soundex，看看它是否符合您的需求。

Answer 4

簽出維基百科上的Soundex算法，您尚未指定語言，但有多種語言的示例實現鏈接。顯然，這會給你一個字符串散列，它對於相似的聲音文字是相同的，並且你想要一個整數，但是你可以應用他們在Boost.Hash中使用的字符串 - >整數散列方法。

編輯：澄清，這裏有一個例子C++實現...

#include <boost/foreach.hpp> 
#include <boost/functional/hash.hpp> 

#include <algorithm> 
#include <string> 
#include <iostream> 

char SoundexChar(char ch) 
{ 
    switch (ch) 
    { 
     case 'B': 
     case 'F': 
     case 'P': 
     case 'V': 
      return '1'; 
     case 'C': 
     case 'G': 
     case 'J': 
     case 'K': 
     case 'Q': 
     case 'S': 
     case 'X': 
     case 'Z': 
      return '2'; 
     case 'D': 
     case 'T': 
      return '3'; 
     case 'M': 
     case 'N': 
      return '5'; 
     case 'R': 
      return '6'; 
     default: 
      return '.'; 
    } 
} 

std::size_t SoundexHash(const std::string& word) 
{ 
    std::string soundex; 
    soundex.reserve(word.length()); 

    BOOST_FOREACH(char ch, word) 
    { 
     if (std::isalpha(ch)) 
     { 
      ch = std::toupper(ch); 

      if (soundex.length() == 0) 
      { 
       soundex.append(1, ch); 
      } 
      else 
      { 
       ch = SoundexChar(ch); 

       if (soundex.at(soundex.length() - 1) != ch) 
       { 
        soundex.append(1, ch); 
       } 
      } 
     } 
    } 

    soundex.erase(std::remove(soundex.begin(), soundex.end(), '.'), soundex.end()); 

    if (soundex.length() < 4) 
    { 
     soundex.append(4 - soundex.length(), '0'); 
    } 
    else if (soundex.length() > 4) 
    { 
     soundex = soundex.substr(0, 4); 
    } 

    return boost::hash_value(soundex); 
} 

int main() 
{ 
    std::cout << "Color = " << SoundexHash("Color") << std::endl; 
    std::cout << "Colour = " << SoundexHash("Colour") << std::endl; 

    std::cout << "Gray = " << SoundexHash("Gray") << std::endl; 
    std::cout << "Grey = " << SoundexHash("Grey") << std::endl; 

    return 0; 
}