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

StackOverflow https://stackoverflow.com/questions/859441

  •  21-08-2019
  •  | 
  •  

Вопрос

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

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

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

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

Спасибо!

Это было полезно?

Решение

Если вам нужны подстроки, Три или Патрика Трие может быть хорошей отправной точкой.

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

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

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

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

Предполагая 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) - но это изменит только числа, поскольку все нормы в конечномерных векторных пространствах эквивалентны.

Другие советы

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

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

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

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

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

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

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

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

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

Вот функция 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
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top