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

Ответ 1

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

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

Идея

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

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

Код

from math import log

# Build a cost dictionary, assuming Zipf 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 тыс. слов, который я собрал из небольшого подмножества Википедии.

До: thumbgreenappleactiveassignmentweeklymetaphor.
После: thumb зеленое яблоко. Активное назначение еженедельной метафоры.

До: там, где есть информация об информации о партиях, о которых говорилось выше, odelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetapho rapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquery whetherthewordisreasonablesowhatsthefastestwayofextractionспасибоalot.

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

До: itwasadarkandstormynight therainfellintorrentsexceptatocial intervalswhenchwatchhecked theaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatsceneliesrattlingalhousetopsandfiercelyagitatingthescantyflameamphelthstthggaggainstthedarkness.

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

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

Оптимизация

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

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

Ответ 2

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

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

Чтобы установить, запустите pip install wordninja.

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

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

https://github.com/keredson/wordninja

Ответ 3

Вот решение, использующее рекурсивный поиск:

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']

Ответ 4

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

• Указатель перемещения (в конкатенированной строке)
• Найдите и сохраните соответствующий node в trie
• Если у trie node есть дочерние элементы (например, есть более длинные слова), перейдите к 1.
• Если node не имеет детей, произошло самое длинное совпадение слов; добавьте слово (сохраненное в node или просто конкатенированное во время trie traversal) в список результатов, reset указатель в trie (или reset ссылка) и начните с

Ответ 5

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

Здесь простое решение с использованием алгоритм Divide and Conquer.

• Он пытается минимизировать количество слов. find_words('cupboard') вернет ['cupboard'], а не ['cup', 'board'] (если предположить, что cupboard, cup и board находятся в словарной строке)
• Оптимальное решение не уникально, реализация ниже возвращает a решение. find_words('charactersin') может вернуться ['characters', 'in'] или, возможно, вернет ['character', 'sin'] (как показано ниже). Вы могли бы легко изменить алгоритм, чтобы вернуть все оптимальные решения.
• В этих реализациях реализованы 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 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 секунд на моей машине 3GHz:

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

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

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

Ответ 8

Вот принятый ответ, переведенный на 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();
}

Ответ 9

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

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

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

Ответ 10

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

Ответ 11

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

https://github.com/dtuggener/CharSplit

Ответ 12

Расширяя предложение @miku об использовании 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 -based из набора слов:

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, does not 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 заранее.

Ответ 13

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

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

Ответ 14

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

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