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

Ответ 1

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

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

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

Ответ 2

Предположим, что у вас есть функция 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. Это также можно адаптировать для перечисления всего решения путем хранения всех таких разделов.

Ответ 3

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

Например: windowsteamblog (http://windowsteamblog.com/ известность)

• windows team blog
• window steam blog

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

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

Ответ 10

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

ИЗМЕНИТЬ

будет "singleemotion" стать "одиночной эмоцией" или "движением греха"?

Ответ 11

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

Ответ 12

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

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(" ");

Ответ 13

Простое решение 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;
    }
}