Как разбить строку на слова. Пример: «строка в слова» -> «Строка в слова»?

Предположим, что у вас есть функция isWord(w), которая проверяет, является ли w словом, используя словарь. Давайте для простоты предположим, что вы хотите знать, возможно ли для некоторого слова w такое разбиение. Это можно легко сделать с помощью динамического программирования.

Пусть S[1..length(w)] - таблица с булевыми записями. S[i] истинно, если слово w[1..i] можно разделить. Тогда зададим S[1] = isWord(w[1]) и для i=2 до length(w) вычислим

S[i] = (isWord[w[1..i] или для любого j в {2..i}: S[j-1] и isWord[j..i]).

Это занимает O(length(w)^2) времени, если запросы к словарю имеют постоянное время. Чтобы действительно найти разбиение, просто храним выигрышное разбиение в каждом S[i], которое установлено в true. Это также может быть адаптировано для перечисления всех решений путем хранения всех таких разбиений.

Должен быть в академической литературе немало об этом. Ключевые слова, которые вы хотите найти, - это сегментация слов . Эта статья , например, выглядит многообещающей.

В общем, вы, вероятно, захотите узнать о моделях Маркова и алгоритме Витерби . Последний представляет собой алгоритм динамического программирования, который может позволить вам найти правдоподобные сегменты для строки без исчерпывающего тестирования всех возможных сегментов. Существенное понимание здесь состоит в том, что если у вас есть n возможных сегментов для первых m символов, и вы хотите найти только наиболее вероятную сегментацию, вам не нужно оценивать каждое из них по сравнению с последующими символами - вам нужно только продолжить оценку наиболее вероятный.

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

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

Лучше всего было бы сравнить подстроку с 0 со словарем, и когда вы нашли совпадение, извлечь это слово и начать новый поиск по словарю с этой точки... но это будет очень подвержено ошибкам, и у вас будут проблемы с множественным числом и апострофами (sinks, sink's), и другими частями речи.

EDIT

станет ли "singleemotion" "единственной эмоцией" или "sin glee motion"?

Рассмотрите огромное количество возможных разделений для данной строки. Если в строке есть n символов, существует n-1 возможных мест для разделения. Например, для строки cat вы можете разбить до a , и вы можете разбить до t . Это приводит к 4 возможным разделениям.

Вы можете рассматривать эту проблему как выбор места разделения строки. Также нужно выбрать, сколько будет расколов.Итак, есть Sum (i = от 0 до n - 1, n - 1 выбрать i) возможных разбиений. Согласно теореме о биномиальном коэффициенте , когда x и y равны 1, это равно pow (2, n-1).

Конечно, большая часть этих вычислений опирается на общие подзадачи, поэтому Динамическое программирование может ускорить ваш алгоритм. Вне всяких сомнений, вычисление логической матрицы M , такой как M [i, j], истинно тогда и только тогда, когда подстрока вашей данной строки от i до j является словом , немного поможет . У вас все еще есть экспоненциальное количество возможных сегментов, но вы могли бы быстро устранить сегментацию, если бы раннее разделение не образовало слово. Тогда решением будет последовательность целых чисел (i0, j0, i1, j1, ...) с условием, что j sub k = i sub (k + 1) .

Если вашей целью является правильный URL-адрес с верблюжьим регистром, я бы обошел проблему и пошел более прямым путем: получить домашнюю страницу для URL-адреса, удалить все пробелы и заглавные буквы из исходного HTML-кода и выполнить поиск вашей строки. Если есть совпадение, найдите этот раздел в исходном HTML и верните его. Вам понадобится массив NumSpaces, который объявляет, сколько пробелов встречается в исходной строке, вот так:

Needle:       isashort    
Haystack:     This is a short phrase    
Preprocessed: thisisashortphrase   
NumSpaces   : 000011233333444444 

И ваш ответ будет следующим:

location = prepocessed.Search(Needle)
locationInOriginal = location + NumSpaces[location]
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location]
Haystack.substring(locationInOriginal, originalLength)

Конечно, это не сработает, если на madduckets.com не будет "Mad Duckets "где-нибудь на главной странице. Увы, это цена, которую вы платите за избежание экспоненциальной проблемы.

Единственный способ разбить эту строку на слова - это использовать словарь. Хотя, наверное, это было бы довольно ресурсоемко.

По сути, это вариант задачи о ранце , поэтому вам нужен полный список слов и любые решения, описанные в Wiki.

С достаточно объемным словарем это будет безумно ресурсоемкая и длительная операция, и вы даже не можете быть уверены, что эта проблема будет решена.

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

Например: windowsteamblog (of http://windowsteamblog.com/ fame)

• windows team blog
• window steam blog