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

Ответ 1

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

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

Ответ 2

Я думаю, что вы ищете расстояние редактирования Levenshtein.

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

Ответ 3

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

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

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

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

Sedgewick также имеет образец кода C.

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

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

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

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

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

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

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

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

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

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

Ответ 4

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

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

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

Исходная установка на этом гарантируется быть меньше O (m ^ 2 + n * t ^ 2), t < m, t * k ~ m, где t - количество признаков для элемента. Это очень разумно и не требует серьезного аппаратного обеспечения.

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

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

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

OP ищет эффективный способ найти наименьшее расстояние hamming (c), а не сама строка. Если у вас есть верхняя граница на 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.

Ответ 10

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

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