Как разбить текст без пробелов на список слов?

Question

Ввод: "tableapplechairtablecupboard..." много слов

Каким будет эффективный алгоритм разделения такого текста на список слов и получения:

Вывод: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

Первое, что приходит в голову, - это пройти через все возможные слова (начиная с первой буквы) и найти самое длинное из возможных слов, продолжить с position=word_position+len(word)

PS
У нас есть список всех возможных слов.
Слово «шкаф» может быть «чашка» и «доска», выбирайте самое длинное.
Язык: python, но главное - сам алгоритм.

Answer 1

На основе решения unutbu я реализовал версию Java:

private static List<String> splitWordWithoutSpaces(String instring, String suffix) {
    if(isAWord(instring)) {
        if(suffix.length() > 0) {
            List<String> rest = splitWordWithoutSpaces(suffix, "");
            if(rest.size() > 0) {
                List<String> solutions = new LinkedList<>();
                solutions.add(instring);
                solutions.addAll(rest);
                return solutions;
            }
        } else {
            List<String> solutions = new LinkedList<>();
            solutions.add(instring);
            return solutions;
        }

    }
    if(instring.length() > 1) {
        String newString = instring.substring(0, instring.length()-1);
        suffix = instring.charAt(instring.length()-1) + suffix;
        List<String> rest = splitWordWithoutSpaces(newString, suffix);
        return rest;
    }
    return Collections.EMPTY_LIST;
}

Ввод: "tableapplechairtablecupboard"

Вывод: [table, apple, chair, table, cupboard]

Вход: "tableprechaun"

Выход: [tab, leprechaun]

Answer 2

Вам необходимо определить свой словарь - возможно, подойдет любой свободный список слов.

После этого используйте этот словарь для построения дерева суффиксов и сопоставьте свой поток ввода с этим: http://en.wikipedia.org/wiki/Suffix_tree

Answer 3

Похоже, что довольно приземлённый откат подойдет.Начните с начала строки.Сканируй прямо, пока не получишь слово.Затем вызовите функцию для остальной части строки.Функция возвращает «ложь», если она сканирует весь путь вправо, не распознавая слово.В противном случае возвращает найденное слово и список слов, возвращаемых рекурсивным вызовом.

Пример: "tableapple".Находит «tab», затем «прыжок», но нет слова в «ple».Нет другого слова в "Леапле".Находит «стол», затем «приложение».«le» не слово, поэтому пытается apple, распознает, возвращает.

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