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

Как упоминалось многими людьми здесь, это стандартная, легкая задача динамического программирования: лучшее решение дает Фальк Хюффнер. Дополнительная информация:

(а) вам следует рассмотреть возможность внедрения isWord с trie, что позволит сэкономить вам много времени, если вы будете использовать правильно (то есть путем постепенного тестирования слов).

(b) написание «динамического программирования сегментации» дает более подробные ответы, начиная с лекций университетского уровня с использованием псевдокодового алгоритма, таких как эта лекция у герцога (что даже позволяет обеспечить простой вероятностный подход к решению делать, когда у вас есть слова, которые не будут содержаться ни в одном словаре).

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

Пусть S[1..length(w)] – таблица с булевыми элементами. S[i] истинно, если слово w[1..i] можно разбить. Затем установите S[1] = isWord(w[1]) и for 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. Это также можно адаптировать для enums всех решений путем хранения всех таких разделов.

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

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

• blog team windows
• window steam blog

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

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

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

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

Конечно, многие из этих вычислений основываются на общих подзадачах, поэтому динамическое программирование может ускорить ваш алгоритм. С вершины моей головы вычисление boolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a word который поможет немного. У вас все еще есть экспоненциальное число возможных сегментов, но вы бы быстро смогли устранить сегментацию, если ранний раскол не сформировал слово. Тогда решением будет последовательность целых чисел (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.

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

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

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

На самом деле это можно сделать (в определенной степени) без словаря. По сути, это проблема неконтролируемого сегментации слов. Вам необходимо собрать большой список доменных имен, применить неконтролируемый алгоритм обучения сегментации (например, Morfessor ) и применить изученную модель для новых доменных имен. Я не уверен, насколько хорошо это сработает (но было бы интересно).

Собственно, со словарем эта проблема может быть решена в O(n) времени. Точнее в (k + 1) * n в худшем случае, где n – количество символов в строке, а k – длина самого длинного слова в словаре.

Кроме того, алгоритм позволяет пропустить нежелательный файл.

Вот рабочая реализация в Common Lisp, которую я создал некоторое время назад: https://gist.github.com/3381522

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

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

РЕДАКТИРОВАТЬ

будет ли «одинокая самооценка» стать «одиночной эмоцией» или «движением греха»?

Я смотрел на проблему и думал, может быть, могу поделиться тем, как я это сделал. Это слишком сложно объяснить мой алгоритм словами, поэтому, возможно, я мог бы поделиться своим оптимизированным решением в псевдокоде:

 string mainword = "stringintowords"; array substrings = get_all_substrings(mainword); /** this way, one does not check the dictionary to check for word validity * on every substring; It would only be queried once and for all, * eliminating multiple travels to the data storage */ string query = "select word from dictionary where word in " + substrings; array validwords = execute(query).getArray(); validwords = validwords.sort(length, desc); array segments = []; while(mainword != ""){ for(x = 0; x < validwords.length; x++){ if(mainword.startswith(validwords[x])) { segments.push(validwords[x]); mainword = mainword.remove(v); x = 0; } } /** * remove the first character if any of valid words do not match, then start again * you may need to add the first character to the result if you want to */ mainword = mainword.substring(1); } string result = segments.join(" "); 

Простое решение Java, которое имеет время работы O (n ^ 2).

 public class Solution { // should contain the list of all words, or you can use any other data structure (eg a Trie) private HashSet dictionary; public String parse(String s) { return parse(s, new HashMap()); } public String parse(String s, HashMap map) { if (map.containsKey(s)) { return map.get(s); } if (dictionary.contains(s)) { return s; } for (int left = 1; left < s.length(); left++) { String leftSub = s.substring(0, left); if (!dictionary.contains(leftSub)) { continue; } String rightSub = s.substring(left); String rightParsed = parse(rightSub, map); if (rightParsed != null) { String parsed = leftSub + " " + rightParsed; map.put(s, parsed); return parsed; } } map.put(s, null); return null; } }