Алгоритм поиска записи нечеткой строки (с поддержкой транспонирования слов и транспонирования символов)

Question

Я пытаюсь найти лучший алгоритм для моего конкретного приложения. Я искал на SO, Google, читал различные статьи о расстояниях Левенштейна и т. Д., Но, честно говоря, это немного выходит за рамки моей компетенции. И большинство, кажется, обнаруживают, насколько похожи две входные строки, как расстояние Хемминга между строками.

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

В моем случае мне нужен нечеткий поиск в базе данных записей музыкальных исполнителей и их альбомов. Как вы можете себе представить, в базе данных будут миллионы записей, поэтому алгоритм, который хорошо масштабируется, имеет решающее значение. На мой вопрос не важно, что Artist и Album находятся в разных столбцах, база данных может просто хранить все слова в одном столбце, если это поможет при поиске.

База данных для поиска:

|-------------------|---------------------|
| Artist            | Album               |
|-------------------|---------------------|
| Alanis Morissette | Jagged Little Pill  |
| Moby              | Everything is Wrong |
| Air               | Moon Safari         |
| Pearl Jam         | Ten                 |
| Nirvana           | Nevermind           |
| Radiohead         | OK Computer         |
| Beck              | Odelay              |
|-------------------|---------------------|

Текст запроса будет содержать от одного слова во всей конкатенации Artist_Album до всей вещи. Текст запроса поступает из OCR и, скорее всего, имеет транспонирование в один символ, но, скорее всего, слова не имеют правильного порядка. Кроме того, в поиске могут быть дополнительные слова, которые не являются частью альбома (например, текст обложки). Например, «OK Computer» может быть вверху альбома, а «Radiohead» - под ним, или в некоторых альбомах текст размещен в столбцах, которые перемешивают порядок слов.

Возможные строки поиска:

C0mputer Rad1ohead
Pearl Ten Jan
Alanis Jagged Morisse11e Litt1e Pi11
Air Moon Virgin Records
Moby Everything

Обратите внимание, что при использовании OCR некоторые буквы будут выглядеть как цифры или полностью неправильные буквы (Ян вместо Jam). А в случае OK Computer Radiohead и Moby Все неправильно *1022* текст запроса даже не содержит всех слов. В случае Air Moon Safari дополнительные слова Virgin Records ищутся, но Safari отсутствует.

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

Answer 1

Давайте разберем проблему на две части.

• Во-первых, вы хотите определить некоторую меру сходства (это называется метрикой). Этот показатель должен возвращать небольшое число, если текст запроса близко соответствует обложке альбома / исполнителя, и возвращать большее число в противном случае.
• Во-вторых, вам нужна структура данных, которая ускоряет этот процесс. Очевидно, что вы не хотите вычислять этот показатель каждый раз, когда выполняется запрос.

часть 1: метрика

Вы уже упомянули расстояние Левенштейна, с которого можно начать. Думай нестандартно, хотя.

LD делает определенные предположения (замена каждого символа одинаково вероятна, удаление равно вероятности вставки и т. Д.). Очевидно, что вы можете улучшить производительность этой метрики, принимая во внимание, какие ошибки OCR, вероятно, внесет.

например. превращение «1» в «я» не должно наказываться так же строго, как превращение «0» в «_».

Я бы реализовал метрику в два этапа. Для любых заданных двух строк:

• разделить обе строки в токенах (в качестве разделителя используйте пробел)
• искать наиболее похожие слова (используя модифицированную версию LD)
• назначить окончательную оценку на основе «совпадающих слов», «пропущенных слов» и «добавленных слов» (желательно взвешенных)

Это пример реализации (возиться с константами):

static double m(String a, String b){
    String[] aParts = a.split(" ");
    String[] bParts = b.split(" ");
    boolean[] bUsed = new boolean[bParts.length];
    int matchedTokens = 0;
    int tokensInANotInB = 0;
    int tokensInBNotInA = 0;
    for(int i=0;i<aParts.length;i++){
        String a0 = aParts[i];
        boolean wasMatched = true;
        for(int j=0;j<bParts.length;j++){
            String b0 = bParts[j];
            double d = levenshtein(a0, b0);
            /* If we match the token a0 with a token from b0
             * update the number of matchedTokens
             * escape the loop
             */
            if(d < 2){
                bUsed[j]=true;
                wasMatched = true;
                matchedTokens++;
                break;
            }
        }
        if(!wasMatched){
            tokensInANotInB++;
        }
    }
    for(boolean partUsed : bUsed){
        if(!partUsed){
            tokensInBNotInA++;
        }
    }
    return (matchedTokens 
    + tokensInANotInB * -0.3  // the query is allowed to contain extra words at minimal cost
    + tokensInBNotInA * -0.5  // the album title should not contain too many extra words
    ) / java.lang.Math.max(aParts.length, bParts.length); 
}

Эта функция использует модифицированную функцию Левенштейна:

static double levenshtein(String x, String y) {
double[][] dp = new double[x.length() + 1][y.length() + 1];

for (int i = 0; i <= x.length(); i++) {
    for (int j = 0; j <= y.length(); j++) {
        if (i == 0) {
            dp[i][j] = j;
        }
        else if (j == 0) {
            dp[i][j] = i;
        }
        else {
            dp[i][j] = min(dp[i - 1][j - 1] 
             + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), 
              dp[i - 1][j] + 1, 
              dp[i][j - 1] + 1);
        }
    }
}
return dp[x.length()][y.length()];
}

Который использует функцию 'стоимость замещения' (которая работает как объяснено)

static double costOfSubstitution(char a, char b){
    if(a == b)
        return 0.0;
    else{
        // 1 and i
        if(a == '1' && b == 'i')
            return 0.5;
        if(a == 'i' && b == '1')
            return 0.5;

        // 0 and O
        if(a == '0' && b == 'o')
            return 0.5;
        if(a == 'o' && b == '0')
            return 0.5;
        if(a == '0' && b == 'O')
            return 0.5;
        if(a == 'O' && b == '0')
            return 0.5;

        // default
        return 1.0; 
    }
}

Я включил только пару примеров (превратив '1' в 'i' или '0' в 'o'). Но я уверен, что вы поняли.

часть 2: структура данных

Посмотрите на BK-деревья . Это специфическая структура данных для хранения метрической информации. Ваша метрика должна быть подлинной метрикой (в математическом смысле слова). Но это легко устроить.