字句類似度を比較するための数値ハッシュ

Question

類似の単語に類似の数値を生成するハッシュアルゴリズムの形式はありますか？偽陽性がたくさんあると思いますが、それは検索プルーニングに役立つようなものです。

EDIT：Soundexのはきちんとしていると便利になるかもしれないが、理想的に、私はこのような何かを振る舞う何かしたい：abs(f('horse') - f('hoarse')) < abs(f('horse') - f('goat'))

Answer 1

何のことをいっていると呼ばれている... C++実装です。これは、さまざまなタイプの入力（画像、音楽、テキスト、宇宙の位置、必要なもの）に適用できます。

残念なことに（検索にもかかわらず）、文字列用のLSHアルゴリズムの実用的な実装が見つかりませんでした。

Answer 2

をSoundexのアルゴリズムは、入力ワードにおける音素に対応するキーの文字列を生成します。 http://www.archives.gov/research/census/soundex.html

文字列間の類似度を比較したい場合は、Levenstein Distanceを試してみてください。 http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

いつでもを試して、あなたのニーズに合っているかどうかを確認できます。

Answer 4

wikipediaのSoundexアルゴリズムをチェックアウトすると、言語は指定されていませんが、ここに複数の言語で実装されたサンプルへのリンクがあります。明らかに、これは類似した発音の単語に対して同じ文字列ハッシュを与え、整数を必要としますが、Boost.Hashで使用する文字列 - >整数ハッシュ法を適用できます。

編集：は明確にするため、ここでの例では、Locality-sensitive Hashing

#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; 
}