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

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

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

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

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

еще раз спасибо Generic Человек!

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. поиск и сохранение соответствующего узла в trie
3. если узел trie имеет дочерние элементы (например, есть более длинные слова), перейдите к 1.
4. если у достигнутого узла нет дочерних элементов, произошло самое длинное совпадение слов; добавьте слово (сохраненное в узел или просто сцепленный во время обхода trie) в список результатов, сбросьте указатель в trie (или сбросьте ссылку) и начните заново

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

вот простое решение с помощью Разделяй и властвуй.

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

код:

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

это займет около 5 секунд на моей машине 3 ГГц:

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

reis массы текстовой информации о комментариях народов, которые анализируются из h t m l, но нет разделенного символа грех их, например, thumb green apple active assignment weekly metaphor по-видимому, есть thumb green apple e t c в строке у меня также есть большой словарь для запроса, является ли слово разумным, поэтому какой самый быстрый способ извлечения t h x много

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

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

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

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

однако, когда у вас есть модель bigram вы может оценить p ('sit down') как биграм против p ('sitdown'), и первый выигрывает. В принципе, если вы не используете биграммы, он рассматривает вероятность слов, которые вы разделяете, как независимые, что не так, некоторые слова, скорее всего, появятся один за другим. К сожалению, это также слова, которые часто склеиваются во многих случаях и смущают разделитель.

вот ссылка на данные (это данные для 3 отдельных проблем, а сегментация только одна. Пожалуйста прочитайте главу для деталей):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 

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

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

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

пример: "tableapple". Находит "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

расширения @Мику!--22--> предложение использовать 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 вверх-фронт.

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

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