Алгоритм поиска кратчайшего предложения, соответствующего шаблону

Question

У меня есть проблема, которую я пытаюсь решить.

Программа получает текстовый файл, содержащий следующие символы: a - z, A - Z, 0 - 9, fullstop (.) Ипространство .Слова в текстовом файле состоят исключительно из аз, аз и 0-9.Программа получает несколько запросов.Каждый запрос состоит из набора полных слов, уже присутствующих в файле.Программа должна вернуть наименьшую фразу из файла, в котором присутствуют все слова (в любом порядке).Если таких фраз много, верните первую.

Вот пример.Допустим, файл содержит:

Bar is doing a computer science degree. Bar has a computer at home. Bar  is now at home.

Запрос 1:

Bar computer a

Ответ:

Bar has a computer

Запрос 2:

Bar home

Ответ:

home. Bar

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

1-й узел "Bar, 0, 1" [Query, start posn, total length].Аналогично для 2-го и 3-го узла.

Поиск следующего компьютера.Минимальное расстояние компьютера для каждого вхождения бара рассчитывается.

1-й узел "Барный компьютер", 0, 5

2-й узел "Барный компьютер", 7, 4 и т. Д. Для других узлов

Далее ищется "а"за.Поиск должен начинаться с начальной позиции, которая упоминается в каждом узле, и должен проходить влево и вправо, пока не будет найдено слово, поскольку порядок не важен.Минимум события должен быть выбран.

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

Если слова уникальны, это станет вариантом TSP?

Answer 1

TSP - не лучший способ подумать об этой проблеме.Пусть n - длина текста, а m - длина запроса;предположим, что n> m.Наивное решение

best = infinity
for i = 1 to n
  for j = i to n
    all_found = true
    for k = 1 to m
      found = false
      for l = i to j
        if text[l] == query[k]
          found = true
      all_found = all_found || found
    if all_found && j - i < best
      best = j - i
      best_i = i
      best_j = j

уже за полиномиальное время в O (n ³ m) для слов ограниченной длины.Теперь давайте оптимизируемся.

Сначала поднимите внутренний цикл с помощью хэш-набора.

best = infinity
for i = 1 to n
  for j = i to n
    subtext_set = {}
    for l = i to j
      subtext_set = subtext_set union {text[l]}
    all_found = true
    for k = 1 to m
      all_found = all_found && query[k] in subtext_set
    if all_found && j - i < best
      best = j - i
      best_i = i
      best_j = j

Время выполнения теперь O (n ³ ) или O (n ³ log n), если вместо этого мы используем бинарное дерево.

Теперь обратите внимание, что расточительно пересчитывать subtext_set, когда верхняя граница увеличивается на единицу.

best = infinity
for i = 1 to n
  subtext_set = {}
  for j = i to n
    subtext_set = subtext_set union {text[l]}
    all_found = true
    for k = 1 to m
      all_found = all_found && query[k] in subtext_set
    if all_found && j - i < best
      best = j - i
      best_i = i
      best_j = j

Мы находимся на O (n ² m).Теперь кажется бесполезным перепроверять весь запрос, когда subtext_set дополняется только одним элементом: почему бы нам просто не проверить его и не вспомнить, сколько нам нужно пройти?

query_set = {}
for k = 1 to m
  query_set = query_set union {query[k]}
best = infinity
for i = 1 to n
  subtext_set = {}
  num_found = 0
  for j = i to n
    if text[l] in query_set && text[l] not in subtext_set
      subtext_set = subtext_set union {text[l]}
      num_found += 1
    if num_found == m && j - i < best
      best = j - i
      best_i = i
      best_j = j

Мы 'в точке O (n ² ).Чтобы добраться до O (n), нужно несколько идей.Во-первых, давайте посмотрим, сколько слов запроса содержится в каждой подстроке для примера

text = Bar has a computer at home. Bar
       1   2   3 4        5  6     7
query = Bar computer a

# j 1 2 3 4 5 6 7
i +--------------
1 | 1 1 2 3 3 3 3
2 | 0 0 1 2 2 2 3
3 | 0 0 1 2 2 2 3
4 | 0 0 0 1 1 1 2
5 | 0 0 0 0 0 0 1
6 | 0 0 0 0 0 0 1
7 | 0 0 0 0 0 0 1

Эта матрица имеет нерастущие столбцы и неубывающие строки, и это в целом верно.Мы хотим пересечь нижнюю сторону записей со значением m, потому что далее это соответствует более длинному решению.Алгоритм заключается в следующем.Если у текущего i, j есть все слова запроса, то увеличьте i;в противном случае увеличьте j.

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

best = infinity
count = hash table whose entries are zero by default
for k = 1 to m
  count[query[k]] = -1
num_found = 0
i = 1
j = 0
while true
  if num_found == m
    if j - i < best
      best = j - i
      best_i = i
      best_j = j
    count[text[i]] -= 1
    if count[text[i]] == -1
      num_found -= 1
    i += 1
  else
    j += 1
    if j > n
        break
    if count[text[j]] == -1
      num_found += 1
    count[text[j]] += 1

Мы достигли O (n).Последняя асимптотически релевантная оптимизация заключается в сокращении использования дополнительного пространства с O (n) до O (m) за счет сохранения количества только для элементов в запросе.Я оставлю это как упражнение.(Кроме того, необходимо уделить больше внимания обработке пустых запросов.)

Answer 2

Для такого рода проблем я рекомендую использовать Суффикс-деревья .