Tokenize valid words from a long string

Question

Tokenize valid words from a long string

Suppose you have a dictionary that contains valid words.

Given an input string with all spaces removed, determine whether the string is composed of valid words or not.

You can assume the dictionary is a hashtable that provides O(1) lookup.

Some examples:

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

If a string has multiple possible parsings, just return true is sufficient.

The string can be very long. Hence think an algorithm that is both space & time efficient.

10

algorithm string parsing

задан SiLent SoNG 24 August 2010 в 06:23

2 ответа

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

Работает следующим образом:

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

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

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

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

0

ответ дан 4 December 2019 в 03:14

Другие вопросы по тегам:

algorithm string parsing

Похожие вопросы:

score 6 · Accepted Answer

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

Например, пусть словарь состоит из слов {летучая мышь, сумка}. Затем строим следующий автомат: состояния обозначим 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 (количеством слов) с подсказкой для построения выше.

В качестве другого примера, со словами {сумка, летучая мышь, булочка, но} автомат будет выглядеть так: alt text

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

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

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