Числовой хеш для сравнения лексического сходства - PullRequest
Новая
       5

Числовой хеш для сравнения лексического сходства

3 голосов
/ 26 июня 2011

Существует ли какая-либо форма алгоритма хеширования, которая выдает похожие числовые значения для похожих слов? Я предполагаю, что было бы много ложных срабатываний, но это похоже на что-то, что может быть полезно для сокращения поиска.

РЕДАКТИРОВАТЬ: Soundex аккуратный и может пригодиться, но в идеале, я хочу что-то, что ведет себя примерно так: abs(f('horse') - f('hoarse')) < abs(f('horse') - f('goat'))

Ответы [ 4 ]

2 голосов
/ 26 июня 2011

Алгоритм Soundex генерирует строки ключей, соответствующие фонемам во входном слове.http://www.archives.gov/research/census/soundex.html

Если вы хотите сравнить только сходство между строками, попробуйте Levenstein Distance.http://en.wikipedia.org/wiki/Levenshtein_distance

1 голос
/ 10 июля 2011

То, о чем вы говорите, называется Хеширование с учетом локальных особенностей . Он может применяться к различным типам ввода (изображения, музыка, текст, позиции в пространстве, все, что вам нужно).

К сожалению (и несмотря на поиск), я не смог найти практической реализации алгоритма LSH для строк.

0 голосов
/ 26 июня 2011

Ознакомьтесь с алгоритмом Soundex в Википедии, вы не указали язык, но там есть ссылки на примеры реализации на нескольких языках. Очевидно, что это даст вам хеш-строку, которая одинакова для похожих звучащих слов, и вы захотите целое число, но затем вы можете применить метод хеширования string-> integer, который они используют в 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;
}
0 голосов
/ 26 июня 2011

Вы всегда можете попробовать Soundex и посмотреть, соответствует ли он вашим потребностям.

...