Обнаружить, скорее всего, слова из текста без пробелов / комбинированных слов

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

Пример:

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

6 Solutions collect form web for “Обнаружить, скорее всего, слова из текста без пробелов / комбинированных слов”

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

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

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

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

Пример:

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

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

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

Попросите людей решить их как капчу на вашем сайте 🙂

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

Я знаю, что этот вопрос отмечен для 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(/[^az\']/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.

Python - лучший язык программирования в мире.