алгоритм поиска ближайшей строки с использованием тех же символов

Question

Учитывая список L из n символьных строк и входную символьную строку S, каков эффективный способ найти символьную строку в L, которая содержит наибольшее количество символов, существующих в S? Мы хотим найти строку в L, которая наиболее близко состоит из букв, содержащихся в S.

Очевидный ответ - перебрать все n строк и проверить, сколько символов в текущей строке существует в S. Однако этот алгоритм будет часто выполняться, и список L из n строк будет храниться в базе данных. ... цикл вручную через все n строк потребует что-то вроде big-Oh, равного n * m ^ 2, где n - количество строк в L, а m - максимальная длина любой строки в L, а также max длина S ... в этом случае m фактически является константой 150.

Есть ли лучший способ, чем просто цикл? Есть ли структура данных, в которую я могу загрузить n строк, что даст мне возможность быстрого поиска? Существует ли алгоритм, который использует предварительно вычисленные метаданные о каждой из n строк, которые будут работать лучше, чем цикл?

Я знаю, что есть много гиков, которые занимаются алгоритмами. Поэтому, пожалуйста, помогите!

Спасибо!

Answer 1

Если вы ищете подстроки, то Trie или Patrica trie могут быть хорошей отправной точкой.

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

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

Это снизит затраты до O(26 * m + n) плюс однократная предварительная обработка, если вы учитываете только латинские буквы без учета регистра.

Если m постоянно, вы можете интерпретировать гистограмму как 26-мерный вектор на 26-мерной единичной сфере, нормализуя ее. Тогда вы можете просто вычислить Dot Product двух векторов, дающих косинус угла между двумя векторами, и это значение должно быть пропорционально сходству строк.

Предполагая m = 3, алфавит A = { 'U', 'V', 'W' } только размера три, и следующий список строк.

L = { "UUU", "UVW", "WUU" }

Гистограммы следующие.

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

Гистограмма h = (x, y, z) нормализуется до h' = (x/r, y/r, z/r) с r евклидовой нормой гистограммы h - то есть r = sqrt(x² + y² + z²).

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

Вход S = "VVW" имеет гистограмму hs = (0, 2, 1) и нормализованную гистограмму hs' = (0.000, 0.894, 0.447).

Теперь мы можем вычислить сходство двух гистограмм h1 = (a, b, c) и h2 = (x, y, z) как евклидово расстояние обеих гистограмм.

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

Для примера получаем.

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

Следовательно, «UVW» наиболее близок к «VVW» (меньшие числа указывают на более высокое сходство).

Используя нормализованные гистограммы h1' = (a', b', c') и h2' = (x', y', z'), мы можем рассчитать расстояние как точечное произведение обеих гистограмм.

d'(h1', h2') = a'x' + b'y' + c'z'

Для примера получаем.

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

Опять же, «UVW» определяется как наиболее близкий к «VVW» (большие цифры указывают на более высокое сходство).

Обе версии дают разные числа, но результаты всегда одинаковы. Можно также использовать другие нормы - например, расстояние Манхэттена (норма L1) - но это изменит только числа, потому что все нормы в конечномерных векторных пространствах эквивалентны.

Answer 2

То, что вы хотите, это BK-Tree . Это немного неинтуитивно, но очень круто - и позволяет искать элементы в пределах порога расстояния Левенштейна (редактировать) за время O (log n).

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

Answer 3

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

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

Answer 4

Вот функция T-SQL, которая отлично работает для меня, дает вам расстояние редактирования:

Пример:

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

Функция:

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END

Answer 5

мне кажется, что порядок символов не важен в вашей задаче, но вы ищете "почти-анаграммы" слова S.

Если это так, то вы можете представить каждое слово в наборе L как массив из 26 целых чисел (при условии, что ваш алфавит состоит из 26 букв). Вы можете представить S аналогично как массив из 26 целых чисел; Теперь, чтобы найти наилучшее совпадение, вы просто пробегаете один раз через набор L и вычисляете метрику расстояния между S-вектором и текущим L-вектором, однако вы хотите определить метрику расстояния (например, евклидово / сумма квадратов или Манхэттен). / сумма абсолютных разностей). Это алгоритм O (n), потому что векторы имеют постоянную длину.

Answer 6

Я считаю, что то, что вы ищете, можно найти здесь: Техника поиска на основе нечеткой логики

Это довольно тяжело, но это то, что вы просите. В нем говорится о сходстве слов и неправильном расположении символов.

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M