Самый быстрый способ найти наиболее похожую строку для ввода?

Question

Учитывая строку запроса Q длины N и список L из M последовательностей длиной ровно N, каков наиболее эффективный алгоритм для поиска строки в L с наименьшим количеством позиций несоответствия Q? Например:

Q = "ABCDEFG";
L = ["ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT"];
answer = L.query(Q);  # Returns "ABCCEFG"
answer2 = L.query("AAAATAA");  #Returns "AAAAAAA".

Очевидный способ - отсканировать каждую последовательность в L, чтобы поиск занял O (M * N). Есть ли способ сделать это в сублинейное время? Мне все равно, есть ли большие начальные затраты на организацию L в какую-то структуру данных, потому что это будет запрашиваться много раз. Кроме того, обработка произвольно связанных результатов хороша.

Редактировать: Чтобы уточнить, я ищу расстояние Хэмминга.

Answer 1

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

Во-первых, это сложная, но стандартная проблема, которая была решена много лет назад. по-разному.

В одном подходе используется три, например, предварительно заданный Седжвик здесь:

http://www.cs.princeton.edu/~rs/strings/

У Седжвика также есть образец кода С.

Я цитирую статью Бентли и Седжвика «Быстрые алгоритмы сортировки и поиска строк»:

"‘ ‘Ближайший сосед" запросов найти все слова в пределах заданного расстояния Хэмминга слова запроса (например, код - это расстояние 2 от соды). Мы даем новый алгоритм поиска ближнего соседа в строках, представляем простую реализацию на C и описываем эксперименты по его эффективности. "

Второй подход заключается в использовании индексации. Разбейте строки на символы n-грамм и индексируйте с инвертированным индексом (проверьте орфографию в Lucene, чтобы узнать, как это делается). Используйте индекс, чтобы вывести потенциальных кандидатов, а затем выполнить дистанцию ​​Хэмминга или отредактировать расстановку кандидатов. Такой подход гарантированно работает лучше (и относительно прост).

Третий появляется в области распознавания речи. Там запрос представляет собой wav-сигнал, а база данных представляет собой набор строк. Существует «таблица», которая сопоставляет части сигнала с частями слова. Цель состоит в том, чтобы найти лучшее совпадение слов для сигнала. Эта проблема известна как выравнивание слов.

В опубликованной проблеме указана неявная стоимость сопоставления частей запроса с частями базы данных. Например, один может иметь разные затраты на удаление / вставку / замену и даже разные затраты на несоответствие, скажем «ph» с «f».

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

Вот ссылка на последний подход:

http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf

Быстрое сопоставление приблизительной строки с суффиксными массивами и анализом A *.

Этот подход применим не только к словам, но и к предложениям.

Answer 2

Хеширование с учетом локальных особенностей лежит в основе того, что кажется лучшим асимптотически известным методом, насколько я понимаю, из этой обзорной статьи в CACM . Сказанная статья довольно волосатая, и я не прочитал все это. См. Также поиск ближайшего соседа .

Чтобы связать эти ссылки с вашей проблемой: все они имеют дело с набором точек в метрическом пространстве, таком как n-мерное векторное пространство. В вашей задаче n - длина каждой строки, а значения в каждой координате - это символы, которые могут появляться в каждой позиции строки.

Answer 3

«Лучший» метод будет значительно отличаться в зависимости от вашего набора ввода и набора запросов. Наличие фиксированной длины сообщения позволит вам рассматривать эту проблему в контексте классификации.

Информационно-теоретический алгоритм дерева решений (например, C4.5) обеспечит наилучшую общую гарантию производительности. Чтобы получить оптимальную производительность от этого метода, вы должны сначала кластеризовать строковые индексы в функции, основанные на взаимной информации. Обратите внимание, что вам нужно изменить классификатор, чтобы он возвращал все конечные узлы в последней ветви, а затем вычислить частичное расстояние редактирования для каждого из них. Расстояние редактирования необходимо рассчитать только для набора объектов, представленного последним разбиением дерева.

Используя эту технику, количество запросов должно составлять ~ O (k log n), k << m, где k - ожидание размера объекта, m - длина строки, а n - количество последовательностей сравнения. </p>

Первоначальная настройка этого параметра гарантированно будет меньше O (m ^ 2 + n * t ^ 2), t

Эти очень хорошие показатели производительности возможны из-за фиксированного ограничения m. Наслаждайтесь!

Answer 4

Вы ищете расстояние Хэмминга между строками (т. Е. Количество различных символов в эквивалентных местах)?

Или для вас также имеет значение расстояние между символами (например, разница между значениями ASCII букв английского алфавита)?

Answer 5

Некоторое разнообразие поиска в первую очередь на целевых последовательностях будет намного лучше, чем O (M * N). Основная идея этого заключается в том, что вы сравниваете первый символ в вашей последовательности-кандидате с первым символом целевых последовательностей, а затем во второй итерации выполняете сравнение только следующих символов с последовательностями, которые имеют наименьшее количество несовпадений и так далее. В вашем первом примере вы будете сравнивать ABCCEFG и AAAAAAA во второй раз, ABCCEFG только третий и четвертый раз, все последовательности в пятый раз и только ABCCEFG после этого. Когда вы доберетесь до конца вашей последовательности-кандидата, набор целевых последовательностей с наименьшим количеством несовпадений будет вашим набором совпадений.

(Примечание: на каждом шаге вы сравниваете со следующим символом для этой ветви поиска. Ни один из прогрессивных сравнений не пропускает символы.)

Answer 6

Вы можете рассматривать каждую последовательность как N-мерную координату, разбивать полученное пространство на блоки, которые знают, какие последовательности в них встречаются, а затем при поиске сначала искать блок последовательности поиска и все смежные блоки, а затем расширяться наружу, если необходимо. (Поддержание нескольких областей чанкинга, вероятно, более желательно, чем поиск действительно больших групп блоков.)

Answer 7

Я думаю, что вы ищете Расстояние Левенштейна для редактирования .

На SO уже есть несколько вопросов по этому поводу , я полагаю, вы можете найти несколько хороших ответов.

Answer 8

Извините, что натолкнулся на эту старую тему

Поэлементный поиск означал бы сложность O (M * N * N) - O (M) для поиска и O (N * N) для вычисления расстояния Левенштейна.

ОП ищет эффективный способ найти наименьшее расстояние Хемминга (с), а не саму струну. Если у вас есть верхняя граница c (скажем, X), вы можете найти наименьшее c в O (log (X) * M * N).

Как указал Стефан, вы можете быстро найти строки в пределах заданного расстояния Хемминга. На этой странице http://blog.faroo.com/2015/03/24/fast-approximate-string-matching-with-large-edit-distances/ рассказывается об одном таком способе использования Tries. Измените это, чтобы просто проверить, есть ли такая строка и двоичный поиск по c от 0 до X.

Answer 9

Я не могу придумать общего, точного алгоритма, который будет меньше, чем O (N * M), но если у вас достаточно малые M и N, вы можете создать алгоритм, который работает как (N + M), используя битовые параллельные операции.

Например, если N и M меньше 16, вы можете использовать таблицу поиска N * M с 64-битными значениями (16 * log2 (16) = 64) и выполнять все операции за один проход через строку где каждая группа из 4 битов в счетчике считает 0-15 для одной из сопоставляемых строк. Очевидно, что вам нужно M log2 (N + 1) бит для хранения счетчиков, поэтому может потребоваться обновить несколько значений для каждого символа, но часто поиск за один проход может быть быстрее, чем другие подходы. Так что на самом деле это O (N * M log (N)), только с более низким постоянным коэффициентом - использование 64-битных целых вводит 1/64, поэтому должно быть лучше, если log2 (N) <64. Если M log2 (N) +1) <64, это работает как (N + M) операций. Но это все еще линейный, а не сублинейный. </p>

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>

size_t match ( const char* string, uint64_t table[][128] ) ;

int main ()
{
    const char* data[] = { "ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT" };
    const size_t N = 7;
    const size_t M = 4;

    // prepare a table
    uint64_t table[7][128] = { 0 };

    for ( size_t i = 0; i < M; ++i )
        for ( size_t j = 0; j < N; ++j )
            table[j][ (size_t)data[i][j] ] |= 1 << (i * 4);

    const char* examples[] = { "ABCDEFG", "AAAATAA", "TTAGQQT", "ZAAGVUT" };

    for ( size_t i = 0; i < 4; ++i ) {
        const char* q = examples[i];
        size_t result = match ( q, table );

        printf("Q(%s) -> %zd %s\n", q, result, data[result]);
    }
}

size_t match ( const char* string, uint64_t table[][128] )
{
    uint64_t count = 0;

    // scan through string once, updating all counters at once
    for ( size_t i = 0; string[i]; ++i )
        count += table[i][ (size_t) string[i] ];

    // find greatest sub-count within count
    size_t best = 0;
    size_t best_sub_count = count & 0xf;

    for ( size_t i = 1; i < 4; ++i ) {
        size_t sub_count = ( count >>= 4 ) & 0xf;

        if ( sub_count > best_sub_count ) {
            best_sub_count = sub_count;
            best = i;
        }
    }

    return best;
}

Answer 10

Если предварительная стоимость не имеет значения, вы можете рассчитать наилучшее совпадение для каждого возможного ввода и поместить результат в хеш-карту.

Конечно, это не сработает, если N не очень мало.