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

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

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

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

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

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

Наивный алгоритм не даст хороших результатов при применении к реальным данным. Вот 20-строчный алгоритм, который использует относительную частоту слов для получения точных результатов для текста реального слова.

(Если вы хотите получить ответ на свой исходный вопрос, в котором не используется частота слов, вам необходимо уточнить, что именно означает «самое длинное слово»: лучше ли иметь слово из 20 букв и десять слов из 3 букв, или лучше иметь пять слов из 10 букв? Как только вы определитесь с точным определением, вам просто нужно изменить определение линии, wordcostчтобы отразить предполагаемое значение.)

Идея

Наилучший способ продолжить - смоделировать распределение выпуска. Хорошее первое приближение - это предположить, что все слова распределены независимо. Тогда вам нужно только знать относительную частоту всех слов. Разумно предположить, что они следуют закону Ципфа, то есть слово с рангом n в списке слов имеет вероятность примерно 1 / ( n log N ), где N - количество слов в словаре.

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

Код

from math import log

# Build a cost dictionary, assuming Zipf's law and cost = -math.log(probability).
words = open("words-by-frequency.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
    """Uses dynamic programming to infer the location of spaces in a string
    without spaces."""

    # Find the best match for the i first characters, assuming cost has
    # been built for the i-1 first characters.
    # Returns a pair (match_cost, match_length).
    def best_match(i):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

    # Build the cost array.
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)
        cost.append(c)

    # Backtrack to recover the minimal-cost string.
    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        assert c == cost[i]
        out.append(s[i-k:i])
        i -= k

    return " ".join(reversed(out))

который вы можете использовать с

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

Результаты

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

Раньше: thumbgreenappleactiveassignment еженедельная метафора.
После: большой палец зеленое яблоко активное задание еженедельная метафора.

Раньше: есть масса текстовой информации людей, комментарии, которые анализируются из HTML, но в них есть ограниченное количество символов.

После: есть масса текстовой информации о комментариях людей, которая анализируется из html, но в них нет разделенных символов, например, метафора активного назначения большого пальца зеленого яблока еженедельная метафора, по-видимому, в строке есть зеленое яблоко большого пальца и т.д. У меня также есть большой словарь для спросите, разумно ли это слово, и какой самый быстрый способ извлечения?

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

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

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

Оптимизация

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

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

Основываясь на отличной работе в верхнем ответе , я создал pipпакет для удобного использования.

>>> import wordninja
>>> wordninja.split('derekanderson')
['derek', 'anderson']

Для установки запустите pip install wordninja.

Единственные отличия незначительны. Это возвращает a, listа не a str, он работает python3, он включает список слов и правильно разбивается, даже если есть не-альфа-символы (например, подчеркивания, тире и т. Д.).

Еще раз спасибо Generic Human!

https://github.com/keredson/wordninja

Вот решение с использованием рекурсивного поиска:

def find_words(instring, prefix = '', words = None):
    if not instring:
        return []
    if words is None:
        words = set()
        with open('/usr/share/dict/words') as f:
            for line in f:
                words.add(line.strip())
    if (not prefix) and (instring in words):
        return [instring]
    prefix, suffix = prefix + instring[0], instring[1:]
    solutions = []
    # Case 1: prefix in solution
    if prefix in words:
        try:
            solutions.append([prefix] + find_words(suffix, '', words))
        except ValueError:
            pass
    # Case 2: prefix not in solution
    try:
        solutions.append(find_words(suffix, prefix, words))
    except ValueError:
        pass
    if solutions:
        return sorted(solutions,
                      key = lambda solution: [len(word) for word in solution],
                      reverse = True)[0]
    else:
        raise ValueError('no solution')

print(find_words('tableapplechairtablecupboard'))
print(find_words('tableprechaun', words = set(['tab', 'table', 'leprechaun'])))

дает

['table', 'apple', 'chair', 'table', 'cupboard']
['tab', 'leprechaun']

Используя структуру данных trie , которая содержит список возможных слов, было бы не слишком сложно сделать следующее:

1. Указатель вперед (в составной строке)
2. Найдите и сохраните соответствующий узел в дереве
3. Если у узла trie есть дочерние элементы (например, есть более длинные слова), перейдите к 1.
4. Если у достигнутого узла нет дочерних узлов, происходит совпадение самого длинного слова; добавить слово (сохраненное в узле или просто объединенное во время обхода дерева) в список результатов, сбросить указатель в дереве (или сбросить ссылку) и начать заново

Решение Unutbu было довольно близким, но я считаю, что код трудно читать, и он не дал ожидаемого результата. Недостаток решения Generic Human состоит в том, что ему нужны частоты слов. Не подходит для всех вариантов использования.

Вот простое решение с использованием алгоритма «разделяй и властвуй» .

1. Он пытается свести к минимуму количество слов Eg find_words('cupboard')будет возвращать , ['cupboard']а не ['cup', 'board'](при условии , что cupboard, cupиboard находятся в dictionnary)
2. Оптимальное решение не является уникальным , реализация ниже доходностей решения. может вернуться или, может быть, он вернетсяfind_words('charactersin')['characters', 'in']['character', 'sin'] (как показано ниже). Вы можете легко изменить алгоритм, чтобы получить все оптимальные решения.
3. В этой реализации решения запоминаются, чтобы запускать их в разумные сроки.

Код:

words = set()
with open('/usr/share/dict/words') as f:
    for line in f:
        words.add(line.strip())

solutions = {}
def find_words(instring):
    # First check if instring is in the dictionnary
    if instring in words:
        return [instring]
    # No... But maybe it's a result we already computed
    if instring in solutions:
        return solutions[instring]
    # Nope. Try to split the string at all position to recursively search for results
    best_solution = None
    for i in range(1, len(instring) - 1):
        part1 = find_words(instring[:i])
        part2 = find_words(instring[i:])
        # Both parts MUST have a solution
        if part1 is None or part2 is None:
            continue
        solution = part1 + part2
        # Is the solution found "better" than the previous one?
        if best_solution is None or len(solution) < len(best_solution):
            best_solution = solution
    # Remember (memoize) this solution to avoid having to recompute it
    solutions[instring] = best_solution
    return best_solution

На моем компьютере с частотой 3 ГГц это займет около 5 секунд:

result = find_words("thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot")
assert(result is not None)
print ' '.join(result)

масса текстовой информации комментариев людей, которая анализируется из html, но в них нет разделенных символов, например, большого пальца, зеленого яблока, активного назначения, еженедельной метафоры, по-видимому, в строке есть большой палец зеленого яблока и т. д., у меня также есть большой словарь, чтобы узнать, есть ли слово разумно, так что какой самый быстрый способ добычи thxa lot

Ответ https://stackoverflow.com/users/1515832/generic-human великолепен. Но лучшая реализация этого, которую я когда-либо видел, была написана самим Питером Норвигом в его книге «Красивые данные».

Прежде чем я вставлю его код, позвольте мне объяснить, почему метод Норвига более точен (хотя и немного медленнее и длиннее с точки зрения кода).

1) Данные немного лучше - как с точки зрения размера, так и с точки зрения точности (он использует подсчет слов, а не простое ранжирование) 2) Что еще более важно, логика, лежащая в основе n-граммов, действительно делает подход настолько точным .

Пример, который он приводит в своей книге, - это проблема разделения струны «сидя». Теперь небиграммный метод разделения строк будет рассматривать p ('sit') * p ('down'), и если это меньше, чем p ('sitdown') - что будет иметь место довольно часто - он НЕ будет разбивать это, но мы бы хотели (большую часть времени).

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

Вот ссылка на данные (это данные для трех отдельных проблем, а сегментация только одна. Пожалуйста, прочтите главу для подробностей): http://norvig.com/ngrams/

а вот ссылка на код: http://norvig.com/ngrams/ngrams.py

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

import re, string, random, glob, operator, heapq
from collections import defaultdict
from math import log10

def memo(f):
    "Memoize function f."
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

def test(verbose=None):
    """Run some tests, taken from the chapter.
    Since the hillclimbing algorithm is randomized, some tests may fail."""
    import doctest
    print 'Running tests...'
    doctest.testfile('ngrams-test.txt', verbose=verbose)

################ Word Segmentation (p. 223)

@memo
def segment(text):
    "Return a list of words that is the best segmentation of text."
    if not text: return []
    candidates = ([first]+segment(rem) for first,rem in splits(text))
    return max(candidates, key=Pwords)

def splits(text, L=20):
    "Return a list of all possible (first, rem) pairs, len(first)<=L."
    return [(text[:i+1], text[i+1:]) 
            for i in range(min(len(text), L))]

def Pwords(words): 
    "The Naive Bayes probability of a sequence of words."
    return product(Pw(w) for w in words)

#### Support functions (p. 224)

def product(nums):
    "Return the product of a sequence of numbers."
    return reduce(operator.mul, nums, 1)

class Pdist(dict):
    "A probability distribution estimated from counts in datafile."
    def __init__(self, data=[], N=None, missingfn=None):
        for key,count in data:
            self[key] = self.get(key, 0) + int(count)
        self.N = float(N or sum(self.itervalues()))
        self.missingfn = missingfn or (lambda k, N: 1./N)
    def __call__(self, key): 
        if key in self: return self[key]/self.N  
        else: return self.missingfn(key, self.N)

def datafile(name, sep='\t'):
    "Read key,value pairs from file."
    for line in file(name):
        yield line.split(sep)

def avoid_long_words(key, N):
    "Estimate the probability of an unknown word."
    return 10./(N * 10**len(key))

N = 1024908267229 ## Number of tokens

Pw  = Pdist(datafile('count_1w.txt'), N, avoid_long_words)

#### segment2: second version, with bigram counts, (p. 226-227)

def cPw(word, prev):
    "Conditional probability of word, given previous word."
    try:
        return P2w[prev + ' ' + word]/float(Pw[prev])
    except KeyError:
        return Pw(word)

P2w = Pdist(datafile('count_2w.txt'), N)

@memo 
def segment2(text, prev='<S>'): 
    "Return (log P(words), words), where words is the best segmentation." 
    if not text: return 0.0, [] 
    candidates = [combine(log10(cPw(first, prev)), first, segment2(rem, first)) 
                  for first,rem in splits(text)] 
    return max(candidates) 

def combine(Pfirst, first, (Prem, rem)): 
    "Combine first and rem results into one (probability, words) pair." 
    return Pfirst+Prem, [first]+rem 

Вот принятый ответ, переведенный на JavaScript (требуется node.js и файл "wordninja_words.txt" из https://github.com/keredson/wordninja ):

var fs = require("fs");

var splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
var maxWordLen = 0;
var wordCost = {};

fs.readFile("./wordninja_words.txt", 'utf8', function(err, data) {
    if (err) {
        throw err;
    }
    var words = data.split('\n');
    words.forEach(function(word, index) {
        wordCost[word] = Math.log((index + 1) * Math.log(words.length));
    })
    words.forEach(function(word) {
        if (word.length > maxWordLen)
            maxWordLen = word.length;
    });
    console.log(maxWordLen)
    splitRegex = new RegExp("[^a-zA-Z0-9']+", "g");
    console.log(split(process.argv[2]));
});


function split(s) {
    var list = [];
    s.split(splitRegex).forEach(function(sub) {
        _split(sub).forEach(function(word) {
            list.push(word);
        })
    })
    return list;
}
module.exports = split;


function _split(s) {
    var cost = [0];

    function best_match(i) {
        var candidates = cost.slice(Math.max(0, i - maxWordLen), i).reverse();
        var minPair = [Number.MAX_SAFE_INTEGER, 0];
        candidates.forEach(function(c, k) {
            if (wordCost[s.substring(i - k - 1, i).toLowerCase()]) {
                var ccost = c + wordCost[s.substring(i - k - 1, i).toLowerCase()];
            } else {
                var ccost = Number.MAX_SAFE_INTEGER;
            }
            if (ccost < minPair[0]) {
                minPair = [ccost, k + 1];
            }
        })
        return minPair;
    }

    for (var i = 1; i < s.length + 1; i++) {
        cost.push(best_match(i)[0]);
    }

    var out = [];
    i = s.length;
    while (i > 0) {
        var c = best_match(i)[0];
        var k = best_match(i)[1];
        if (c == cost[i])
            console.log("Alert: " + c);

        var newToken = true;
        if (s.slice(i - k, i) != "'") {
            if (out.length > 0) {
                if (out[-1] == "'s" || (Number.isInteger(s[i - 1]) && Number.isInteger(out[-1][0]))) {
                    out[-1] = s.slice(i - k, i) + out[-1];
                    newToken = false;
                }
            }
        }

        if (newToken) {
            out.push(s.slice(i - k, i))
        }

        i -= k

    }
    return out.reverse();
}

Если вы предварительно скомпилируете список слов в DFA (что будет очень медленно), то время, необходимое для сопоставления ввода, будет пропорционально длине строки (на самом деле, только немного медленнее, чем просто итерация по строке).

По сути, это более общая версия алгоритма trie, о котором упоминалось ранее. Я упоминаю это только для полноты - пока нет реализации DFA, которую можно было бы просто использовать. RE2 будет работать, но я не знаю, позволяют ли привязки Python настраивать размер DFA до того, как он просто выбрасывает скомпилированные данные DFA и выполняет поиск NFA.

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

Пример: «яблочный стол». Находит «tab», затем «leap», но нет слова в «ple». Другого слова в слове «leapple» нет. Находит «стол», затем «приложение». «ле» ни слова, поэтому пробует яблоко, распознает, возвращает.

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

На основе решения 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]

Для немецкого языка есть CharSplit, который использует машинное обучение и неплохо работает со строками из нескольких слов.

https://github.com/dtuggener/CharSplit

Расширяя предложение @miku об использовании a Trie, добавление только для добавления Trieотносительно просто реализовать в python:

class Node:
    def __init__(self, is_word=False):
        self.children = {}
        self.is_word = is_word

class TrieDictionary:
    def __init__(self, words=tuple()):
        self.root = Node()
        for word in words:
            self.add(word)

    def add(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, Node())
        node.is_word = True

    def lookup(self, word, from_node=None):
        node = self.root if from_node is None else from_node
        for c in word:
            try:
                node = node.children[c]
            except KeyError:
                return None

        return node

Затем мы можем построить Trieсловарь на основе набора слов:

dictionary = {"a", "pea", "nut", "peanut", "but", "butt", "butte", "butter"}
trie_dictionary = TrieDictionary(words=dictionary)

В результате получится дерево, которое выглядит следующим образом ( *указывает начало или конец слова):

* -> a*
 \\\ 
  \\\-> p -> e -> a*
   \\              \-> n -> u -> t*
    \\
     \\-> b -> u -> t*
      \\             \-> t*
       \\                 \-> e*
        \\                     \-> r*
         \
          \-> n -> u -> t*

Мы можем включить это в решение, объединив его с эвристикой о том, как выбирать слова. Например, мы можем предпочесть более длинные слова более коротким словам:

def using_trie_longest_word_heuristic(s):
    node = None
    possible_indexes = []

    # O(1) short-circuit if whole string is a word, doesn't go against longest-word wins
    if s in dictionary:
        return [ s ]

    for i in range(len(s)):
        # traverse the trie, char-wise to determine intermediate words
        node = trie_dictionary.lookup(s[i], from_node=node)

        # no more words start this way
        if node is None:
            # iterate words we have encountered from biggest to smallest
            for possible in possible_indexes[::-1]:
                # recurse to attempt to solve the remaining sub-string
                end_of_phrase = using_trie_longest_word_heuristic(s[possible+1:])

                # if we have a solution, return this word + our solution
                if end_of_phrase:
                    return [ s[:possible+1] ] + end_of_phrase

            # unsolvable
            break

        # if this is a leaf, append the index to the possible words list
        elif node.is_word:
            possible_indexes.append(i)

    # empty string OR unsolvable case 
    return []

Мы можем использовать эту функцию так:

>>> using_trie_longest_word_heuristic("peanutbutter")
[ "peanut", "butter" ]

Потому что мы сохраняем нашу позицию в , Trieкак мы искать дольше и более длинные слова, обход trieне более одного раза за возможным решение (а не 2раз для peanut: pea, peanut). Последнее короткое замыкание избавляет нас от хождения по струне в худшем случае.

Конечный результат - это всего лишь несколько проверок:

'peanutbutter' - not a word, go charwise
'p' - in trie, use this node
'e' - in trie, use this node
'a' - in trie and edge, store potential word and use this node
'n' - in trie, use this node
'u' - in trie, use this node
't' - in trie and edge, store potential word and use this node
'b' - not in trie from `peanut` vector
'butter' - remainder of longest is a word

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

Недостатками этого решения являются большой объем памяти trieи затраты на предварительную trieсборку.

Если у вас есть исчерпывающий список слов, содержащихся в строке:

word_list = ["table", "apple", "chair", "cupboard"]

Использование понимания списка для перебора списка, чтобы найти слово и сколько раз оно встречается.

string = "tableapplechairtablecupboard"

def split_string(string, word_list):

    return ("".join([(item + " ")*string.count(item.lower()) for item in word_list if item.lower() in string])).strip()

Функция возвращает stringвывод слов в порядке спискаtable table apple chair cupboard

Большое спасибо за помощь в https://github.com/keredson/wordninja/

Небольшой вклад того же самого в Java с моей стороны.

Открытый метод splitContiguousWordsможет быть встроен с двумя другими методами в класс, имеющий файл ninja_words.txt в том же каталоге (или изменен по выбору кодировщика). И метод splitContiguousWordsможно было использовать для этой цели.

public List<String> splitContiguousWords(String sentence) {

    String splitRegex = "[^a-zA-Z0-9']+";
    Map<String, Number> wordCost = new HashMap<>();
    List<String> dictionaryWords = IOUtils.linesFromFile("ninja_words.txt", StandardCharsets.UTF_8.name());
    double naturalLogDictionaryWordsCount = Math.log(dictionaryWords.size());
    long wordIdx = 0;
    for (String word : dictionaryWords) {
        wordCost.put(word, Math.log(++wordIdx * naturalLogDictionaryWordsCount));
    }
    int maxWordLength = Collections.max(dictionaryWords, Comparator.comparing(String::length)).length();
    List<String> splitWords = new ArrayList<>();
    for (String partSentence : sentence.split(splitRegex)) {
        splitWords.add(split(partSentence, wordCost, maxWordLength));
    }
    log.info("Split word for the sentence: {}", splitWords);
    return splitWords;
}

private String split(String partSentence, Map<String, Number> wordCost, int maxWordLength) {
    List<Pair<Number, Number>> cost = new ArrayList<>();
    cost.add(new Pair<>(Integer.valueOf(0), Integer.valueOf(0)));
    for (int index = 1; index < partSentence.length() + 1; index++) {
        cost.add(bestMatch(partSentence, cost, index, wordCost, maxWordLength));
    }
    int idx = partSentence.length();
    List<String> output = new ArrayList<>();
    while (idx > 0) {
        Pair<Number, Number> candidate = bestMatch(partSentence, cost, idx, wordCost, maxWordLength);
        Number candidateCost = candidate.getKey();
        Number candidateIndexValue = candidate.getValue();
        if (candidateCost.doubleValue() != cost.get(idx).getKey().doubleValue()) {
            throw new RuntimeException("Candidate cost unmatched; This should not be the case!");
        }
        boolean newToken = true;
        String token = partSentence.substring(idx - candidateIndexValue.intValue(), idx);
        if (token != "\'" && output.size() > 0) {
            String lastWord = output.get(output.size() - 1);
            if (lastWord.equalsIgnoreCase("\'s") ||
                    (Character.isDigit(partSentence.charAt(idx - 1)) && Character.isDigit(lastWord.charAt(0)))) {
                output.set(output.size() - 1, token + lastWord);
                newToken = false;
            }
        }
        if (newToken) {
            output.add(token);
        }
        idx -= candidateIndexValue.intValue();
    }
    return String.join(" ", Lists.reverse(output));
}


private Pair<Number, Number> bestMatch(String partSentence, List<Pair<Number, Number>> cost, int index,
                      Map<String, Number> wordCost, int maxWordLength) {
    List<Pair<Number, Number>> candidates = Lists.reverse(cost.subList(Math.max(0, index - maxWordLength), index));
    int enumerateIdx = 0;
    Pair<Number, Number> minPair = new Pair<>(Integer.MAX_VALUE, Integer.valueOf(enumerateIdx));
    for (Pair<Number, Number> pair : candidates) {
        ++enumerateIdx;
        String subsequence = partSentence.substring(index - enumerateIdx, index).toLowerCase();
        Number minCost = Integer.MAX_VALUE;
        if (wordCost.containsKey(subsequence)) {
            minCost = pair.getKey().doubleValue() + wordCost.get(subsequence).doubleValue();
        }
        if (minCost.doubleValue() < minPair.getKey().doubleValue()) {
            minPair = new Pair<>(minCost.doubleValue(), enumerateIdx);
        }
    }
    return minPair;
}

Это поможет

from wordsegment import load, segment
load()
segment('providesfortheresponsibilitiesofperson')

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

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