Токенизируйте правильные слова из длинной строки

Question

Предположим, у вас есть словарь, содержащий правильные слова.

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

Можно предположить, что словарь является хеш-таблицей, которая обеспечивает поиск O (1).

Some examples:

helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid

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

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

Answer 1

Я думаю, что множество всех строк, которые встречаются как конкатенация допустимых слов (слов, взятых из конечного словаря), образуют обычный язык над алфавитом символов. Затем вы можете построить конечный автомат, который принимает именно те строки, которые вы хотите; время вычисления O (n).

Например, пусть словарь состоит из слов {bat, bag}. Затем мы строим следующий автомат: состояния обозначаются 0, 1, 2. Края: (0,1, b), (1,2, a), (2,0, t), (2,0, g) ; где тройка (x, y, z) означает ребро, ведущее от x к y на входе z. Единственное принимающее состояние - 0. На каждом шаге при чтении следующего входного знака вы должны вычислить набор состояний, которые достижимы на этом входном сигнале. Учитывая, что число состояний в автомате постоянно, оно имеет сложность O (n). Что касается сложности пространства, я думаю, что вы можете сделать с O (количество слов) с подсказкой для конструкции выше.

В другом примере со словами {bag, bat, bun, но} автомат будет выглядеть так:

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

1. Пусть S - набор состояний, изначально содержащий начальное состояние.
2. Прочитайте следующий вводимый символ, обозначим его как.
3. Для каждого элемента s в S определите состояние, в которое мы переходим из s при чтении a; то есть состояние r такое, что с обозначениями выше (s, r, a) является ребром. Обозначим множество этих состояний через R. То есть R = {r | s в S, (s, r, a) - ребро}.
4. (Если R пусто, строка не принимается и алгоритм останавливается.)
5. Если входных символов больше нет, проверьте, находится ли какое-либо из принимающих состояний в R. (В нашем случае, есть только одно принимающее состояние, начальное состояние.) Если это так, строка принимается, если нет, строка не принята.
6. В противном случае возьмите S: = R и перейдите к 2.

Теперь количество выполнений этого цикла равно количеству входных символов. Единственное, что мы должны исследовать, это то, что шаги 3 и 5 занимают постоянное время. Учитывая, что размер S и R не превышает число состояний в автомате, которое является постоянным, и что мы можем хранить ребра таким образом, чтобы время поиска было постоянным, это следует. (Обратите внимание, что мы, конечно, теряем несколько «разборов», но это также не было требованием.) Я думаю, что это на самом деле называется проблемой членства для обычных языков, но я не смог найти подходящую онлайн-справку.

Answer 2

Я бы пошел на рекурсивный алгоритм с неявным возвратом. Сигнатура функции: f: input -> result, где input - строка, result или true или false, в зависимости от того, можно ли всю строку токенизировать правильно.

Работает так:

1. Если input - пустая строка, вернуть true.
2. Посмотрите на префикс длины один input (т. Е. Первый символ). Если он находится в словаре, запустите f с суффиксом input. Если это возвращает true, верните также true.
3. Если префикса длины один из предыдущего шага нет в словаре, или при вызове f на предыдущем шаге возвращается false, увеличьте префикс на единицу и повторите на шаге 2. Если префикс невозможно сделать больше (уже в конце строки), вернуть false.
4. Сполосните и повторите.

Для словарей с небольшим или умеренным количеством неоднозначных префиксов, это должно принести довольно хорошее время выполнения на практике (я бы сказал, O (n) в среднем случае), хотя в теории, патологические случаи со сложностью O (2 ^ n), вероятно, могут быть построены. Тем не менее, я сомневаюсь, что мы можем добиться большего успеха, так как в любом случае нам нужно возвращаться назад, поэтому «инстинктивный» подход O (n) с использованием обычного предварительно вычисленного лексера исключен. ... я думаю.

РЕДАКТИРОВАТЬ: оценка сложности среднего случая, вероятно, неверно, см. Мой комментарий.

Пространственная сложность будет только пространством стека, поэтому O (n) даже в худшем случае.