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

Question

Как правильно разбить строку на слова? (строка не содержит пробелов или знаков пунктуации)

Например: "stringintowords" -> "Строка в слова"

Не могли бы вы порекомендовать, какой алгоритм следует использовать здесь?

! Обновление: для тех, кто считает этот вопрос просто ради любопытства. Этот алгоритм может использоваться для маскировки доменных имен ("sportandfishing .com" -> "SportAndFishing .com"), и этот алгоритм в настоящее время используется aboutus dot org для динамического преобразования.

Answer 1

Предположим, у вас есть функция 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 (длина (w) ^ 2) времени, если запросы словаря имеют постоянное время. Чтобы найти расщепление, просто сохраните выигрышное расщепление в каждом S [i], для которого установлено значение true. Это также может быть адаптировано для перечисления всего решения путем сохранения всех таких разбиений.

Answer 2

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

(a) вам следует рассмотреть возможность реализации isWord с помощью дерева, которое сэкономит вам много времени при правильном использовании (то есть путем поэтапного тестирования на наличие слов).

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

Answer 3

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

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

Answer 4

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

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

• windows team blog
• window steam blog

Answer 5

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

Вы можете рассматривать эту проблему как выбор места, где нужно разбить строку.Вам также нужно выбрать, сколько будет разделений.Таким образом, есть 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, япозволит обойти проблему и перейти к чему-то более прямому: получить домашнюю страницу для 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" где-то на главной странице.Увы, это цена, которую вы платите, чтобы избежать экспоненциальной проблемы.

Answer 6

На самом деле, с помощью словаря эту проблему можно решить за O(n) время. Точнее, в худшем случае (k + 1) * n, где n - это количество символов в строке, а k - длина самого длинного слова в словаре.

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

Answer 10

Простое Java-решение с O (n ^ 2) временем выполнения.

public class Solution {
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie)
    private HashSet<String> dictionary;

    public String parse(String s) {
        return parse(s, new HashMap<String, String>());
    }

    public String parse(String s, HashMap<String, String> 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;
    }
}