Обнаружить, скорее всего, слова из текста без пробелов/комбинированных слов
Есть ли хорошая библиотека для обнаружения и разделения слов из комбинированной строки?
Пример:
"cdimage" -> ["cd", "image"]
"filesaveas" -> ["file", "save", "as"]
Ответы
Ответ 1
Здесь представлено решение динамического программирования (реализовано как 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'])
Ответ 2
Я не знаю ни одной библиотеки для нее, но не сложно реализовать основные функции.
- Получить список слов, например UNIX
words
.
- Настройте содержимое своего списка слов в trie.
- Возьмите строку, которую хотите разбить, и следуйте ее пути в trie. Каждый раз, когда вы достигаете действительного слова, создайте новую ветку, которая ищет слово, начинающееся с точки, в которой вы столкнулись. Как только вы закончите свою текущую ветку, вернитесь к той, которую вы создали, как в глубине первого поиска.
- Разбить получаемые списки вручную, используя эвристику или через парсер естественного языка.
Пример:
- Слово: "filesaveasstring"
- Первое действующее слово - "файл". Попробуйте сопоставить "saveas". Первое действующее слово - "сохранить". Попробуйте сопоставить "asstring". Первое действительное слово - "как". Попробуйте сопоставить "string". Первое действительное слово - "строка". Согласовано до конца; поместите [файл сохранить как строку] в список результатов.
- Backtrack для соответствия "string" - никаких других возможностей. Откат к "asstring". Первое неиспользуемое действительное слово - "задница". Попробуйте выполнить "tring". Нет возможных совпадений. Откат к "asstring". Нет возможных совпадений. Возвратитесь к "filesaveasstring" .
- Первый непосещенный матч - это "файлы". Попробуйте сопоставить "aveasstring". Первый матч - "ave". Попробуйте сопоставить "asstring" (то же, что и шаги 2/3), добавив [файлы ave в виде строки] в список результатов и вернуться к началу.
- Попробуйте сопоставить "filesaveasstring" . Нет приглашенных матчей. Готово.
- Выберите наиболее вероятный вариант из [[сохранение файла как строки] [файлы ave в виде строки]] с помощью эвристического или парсера естественного языка.
Ответ 3
Попросите людей решить их как капчу на вашем сайте:)
Ответ 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']]
Ответ 5
Если вы не делаете это для удовольствия, но на самом деле делаете что-то для работы и т.д., мой совет - решить это в источнике. Почему у вас эти комбинации объединены? Откуда у вас эти струны? Если это возможно, вставьте пробелы в источник, откуда происходят эти строки.
Ответ 6
Я знаю, что этот вопрос отмечен для 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.