Определить наиболее вероятные слова из текста без пробелов / комбинированных слов

Question

Есть ли хорошая библиотека, способная обнаруживать и разбивать слова из объединенной строки?

Пример:

"cdimage" -> ["cd", "image"]
"filesaveas" -> ["file", "save", "as"]

Answer 1

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

WORD_FREQUENCIES = {
    'file': 0.00123,
    'files': 0.00124,
    'save': 0.002,
    'ave': 0.00001,
    'as': 0.00555
}

def split_text(text, word_frequencies, cache):
    if text in cache:
        return cache[text]
    if not text:
        return 1, []
    best_freq, best_split = 0, []
    for i in xrange(1, len(text) + 1):
        word, remainder = text[:i], text[i:]
        freq = word_frequencies.get(word, None)
        if freq:
            remainder_freq, remainder = split_text(
                    remainder, word_frequencies, cache)
            freq *= remainder_freq
            if freq > best_freq:
                best_freq = freq
                best_split = [word] + remainder
    cache[text] = (best_freq, best_split)
    return cache[text]

print split_text('filesaveas', WORD_FREQUENCIES, {})

--> (1.3653e-08, ['file', 'save', 'as'])

Answer 2

Я не знаю ни одной библиотеки для него, но не должно быть сложно реализовать основные функции.

1. Получить список слов, как в UNIX words.
2. Заполните содержимое вашего списка слов в три.
3. Возьмите строку, которую вы хотите разделить, и следуйте по ее пути в дереве. Каждый раз, когда вы достигаете правильного слова, создайте новую ветвь, которая ищет слово, начиная с точки строки, к которой вы попали. Как только вы закончите свою текущую ветку, вернитесь к той, которую вы создали, как при глубоком поиске.
4. Устранить неоднозначность полученных списков вручную, используя эвристику или анализатор естественного языка.

Пример:

1. Слово: "filesaveasstring"
2. Первое допустимое слово - «файл». Попробуйте сопоставить «saveas». Первое правильное слово «сохранить». Попробуйте сопоставить "asstring". Первое действительное слово «как». Попробуйте сопоставить «строку». Первое допустимое слово - «строка». Совпадение до конца; поместите [файл сохранить как строку] в ваш список результатов.
3. Возврат к соответствующей «строке» - других возможностей нет. Возврат к «asstring». Первое не посещаемое действительное слово - "задница" Попробуйте сопоставить «tring». Нет возможных совпадений. Возврат к «asstring». Нет возможных совпадений. Возврат к "filesaveasstring".
4. Первый не посещаемый матч - это «файлы». Попробуйте сопоставить «aveasstring». Первый матч "пр." Попробуйте сопоставить «asstring» (те же результаты, что и шаги 2/3), добавив [files ave as string] в свой список результатов и вернувшись в начало.
5. Попробуйте сопоставить "filesaveasstring". Нет посещенных матчей. Готово.
6. Выберите наиболее вероятное из [[файл сохранить как строку] [файлы ave как строка]], используя эвристический или синтаксический анализатор естественного языка.

Answer 3

Заставьте людей решать их как капчу на вашем сайте :) 1001 *

Answer 4

Я не знаю библиотеку, которая делает это, но написать ее несложно, если у вас есть список слов:

wordList = file('words.txt','r').read().split()
words = set( s.lower() for s in wordList )

def splitString(s):
    found = []

    def rec(stringLeft, wordsSoFar):
        if not stringLeft:
            found.append(wordsSoFar)
        for pos in xrange(1, len(stringLeft)+1):
            if stringLeft[:pos] in words:
                rec(stringLeft[pos:], wordsSoFar + [stringLeft[:pos]])

    rec(s.lower(), [])
    return found

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

Пример:

>>> splitString('filesaveas')
[['file', 'save', 'as'], ['files', 'ave', 'as']]

Answer 5

Я знаю, что этот вопрос помечен для Python, но мне нужна была реализация JavaScript. Исходя из предыдущих ответов, я решил поделиться своим кодом. Кажется, работает прилично.

function findWords(input){
    input = input.toLowerCase().replace(/\s/g, ""); //Strip whitespace

    var index = 0;
    var validWords = [];
    for (var len = input.length; len > 0; len--){ //Go backwards as to favor longer words
        var testWord = input.substr(index, len);
        var dictIndex = _dictionary.indexOf(testWord.replace(/[^a-z\']/g, "")); //Remove non-letters
        if (dictIndex != -1){
            validWords.push(testWord);
            if (len == input.length){
                break; //We are complete
            }
            var nextWords = findWords(input.substr(len, input.length - len)); //Recurse
            if (!nextWords.words.length){ //No further valid words
                validWords.pop();
            }
            validWords = validWords.concat(nextWords.words);
            if (nextWords.complete === true){
                break; //Cascade complete
            }
        }
    }
    return {
        complete:len > 0, //We broke which indicates completion
        words:validWords
    };
}

Примечание: "_dictionary" должен быть массивом слов, отсортированных по частоте. Я использую словарь из Project Gutenberg.

Answer 6

если вы делаете это не для развлечения, а на самом деле что-то делаете для работы и т. Д., Мой совет - заняться этим у источника.Почему у вас эти строки объединены?Где вы взяли эти строки?Если это возможно, вставьте пробелы в источнике, откуда эти строки.