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

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

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

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

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

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

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

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

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

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

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

Конечно, это не будет работать, если N не будет exremely маленький.

Я не могу думать об общем, точном алгоритме, который будет меньше, чем 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 журнал (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;
}