用于比较词汇相似性的数字哈希

Question

是否有一种哈希算法可以为相似单词生成类似的数字值？我想可能会有许多误判，但这似乎对于搜索修剪可能是有用的。

编辑：Soundex很不错，可能会派上用场，但理想情况下，我希望有一些行为类似于这样的东西：abs(f('horse') - f('hoarse')) < abs(f('horse') - f('goat'))

- Eric Pruitt

---

@Cicada，你能把这个作为答案提交吗？即使没有我想要的语言的实现，这正是我要找的。 - Eric Pruitt

Answer 1

声纳算法生成与输入单词中的音素相对应的键字符串。http://www.archives.gov/research/census/soundex.html 如果您只想比较字符串之间的相似性，请尝试使用Levenstein距离。http://en.wikipedia.org/wiki/Levenshtein_distance

- Andreas Jansson

---

在阅读这个页面后，我发现另一个算法是 http://en.wikipedia.org/wiki/Metaphone 。此外，我还发现了一篇博客文章，讨论了一个家谱网站如何使用多种方法：http://www.geneamusings.com/2014/04/working-with-mocavo-sliders-post-2.html - shawad

Answer 2

你所说的是称为局部敏感哈希的技术。它可以应用于不同类型的输入（图像、音乐、文本、空间位置等等，任何你需要的）。但是，很遗憾（尽管我已经搜索过），我没有找到任何实际实现字符串LSH算法的例子。

- user703016

Answer 3

在维基百科上查看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;
}

- Node

Answer 4

你可以尝试使用Soundex，看看它是否符合你的需求。

- Jonas Elfström