Как я могу разделить несколько слов?
У меня есть массив около 1000 записей, с примерами ниже:
wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector
Я хотел бы иметь возможность разделить их на соответствующие слова, как:
wicked weather
liquid weather
drive our trucks
go compact
slim projector
Я надеялся, что регулярное выражение может сделать свое дело. Но, поскольку нет границы, на которой можно остановиться, и нет какой-либо заглавной буквы, на которой я мог бы остановиться, я думаю, что какая-то ссылка на словарь может быть необходима?
Я предполагаю, что это можно сделать вручную, но почему - когда это можно сделать с помощью кода! =) Но это поставило меня в тупик. Есть идеи?
16 ответов
Может ли человек сделать это?
farsidebag дальняя сумка дальняя сумка дальняя сторона сумки
Мало того, что вам нужно использовать словарь, вам, возможно, придется использовать статистический подход, чтобы выяснить, что наиболее вероятно (или, не дай бог, фактический HMM для вашего человеческого языка по вашему выбору...)
Для того, чтобы сделать статистику, которая может быть полезной, я обращаюсь к доктору Питеру Норвигу, который решает другую, но связанную проблему проверки правописания в 21 строке кода: http://norvig.com/spell-correct.html
(он немного обманывает, складывая каждый цикл for в одну строку... но все же).
Обновление Это застряло в моей голове, поэтому мне пришлось родить его сегодня. Этот код выполняет разделение, аналогичное описанному Робертом Гэмблом, но затем он упорядочивает результаты на основе частоты слов в предоставленном файле словаря (который теперь, как ожидается, будет некоторым текстовым представителем вашего домена или английского в целом. Я использовал большой.txt от Norvig, ссылка на которую приведена выше, и добавила к ней словарь, чтобы покрыть пропущенные слова).
Комбинация из двух слов в большинстве случаев побьет комбинацию из 3 слов, если только разница в частотах не огромна.
Я разместил этот код с некоторыми незначительными изменениями в своем блоге
http://squarecog.wordpress.com/2008/10/19/splitting-words-joined-into-a-single-string/ а также написал немного об ошибке в этом коде. Я был просто соблазнен тихо исправить это, но подумал, что это может помочь некоторым людям, которые раньше не видели трюк с журналом: http://squarecog.wordpress.com/2009/01/10/dealing-with-underflow-in-joint-probability-calculations/
Вывод на ваши слова, плюс несколько моих собственных - обратите внимание, что происходит с "orcore":
perl splitwords.pl big.txt words answerveal: 2 возможности - ответ телятина - ответь все wickedweather: 4 возможности - злая погода - злые мы на нее - плохая погода - злословил мы на нее Liquidweather: 6 возможностей - жидкая погода - жидкий мы у нее - хорошая погода - мы за нее - погода погоды - Ли Цюй мы на нее Driveourtrucks: 1 возможности - водить наши грузовики гокомпакт: 1 возможность - иди компактно слипроектор: 2 возможности - тонкий проектор - тонкий проект или orcore: 3 возможности - или ядро - или ко - руда орков
Код:
#!/usr/bin/env perl
use strict;
use warnings;
sub find_matches($);
sub find_matches_rec($\@\@);
sub find_word_seq_score(@);
sub get_word_stats($);
sub print_results($@);
sub Usage();
our(%DICT,$TOTAL);
{
my( $dict_file, $word_file ) = @ARGV;
($dict_file && $word_file) or die(Usage);
{
my $DICT;
($DICT, $TOTAL) = get_word_stats($dict_file);
%DICT = %$DICT;
}
{
open( my $WORDS, '<', $word_file ) or die "unable to open $word_file\n";
foreach my $word (<$WORDS>) {
chomp $word;
my $arr = find_matches($word);
local $_;
# Schwartzian Transform
my @sorted_arr =
map { $_->[0] }
sort { $b->[1] <=> $a->[1] }
map {
[ $_, find_word_seq_score(@$_) ]
}
@$arr;
print_results( $word, @sorted_arr );
}
close $WORDS;
}
}
sub find_matches($){
my( $string ) = @_;
my @found_parses;
my @words;
find_matches_rec( $string, @words, @found_parses );
return @found_parses if wantarray;
return \@found_parses;
}
sub find_matches_rec($\@\@){
my( $string, $words_sofar, $found_parses ) = @_;
my $length = length $string;
unless( $length ){
push @$found_parses, $words_sofar;
return @$found_parses if wantarray;
return $found_parses;
}
foreach my $i ( 2..$length ){
my $prefix = substr($string, 0, $i);
my $suffix = substr($string, $i, $length-$i);
if( exists $DICT{$prefix} ){
my @words = ( @$words_sofar, $prefix );
find_matches_rec( $suffix, @words, @$found_parses );
}
}
return @$found_parses if wantarray;
return $found_parses;
}
## Just a simple joint probability
## assumes independence between words, which is obviously untrue
## that's why this is broken out -- feel free to add better brains
sub find_word_seq_score(@){
my( @words ) = @_;
local $_;
my $score = 1;
foreach ( @words ){
$score = $score * $DICT{$_} / $TOTAL;
}
return $score;
}
sub get_word_stats($){
my ($filename) = @_;
open(my $DICT, '<', $filename) or die "unable to open $filename\n";
local $/= undef;
local $_;
my %dict;
my $total = 0;
while ( <$DICT> ){
foreach ( split(/\b/, $_) ) {
$dict{$_} += 1;
$total++;
}
}
close $DICT;
return (\%dict, $total);
}
sub print_results($@){
#( 'word', [qw'test one'], [qw'test two'], ... )
my ($word, @combos) = @_;
local $_;
my $possible = scalar @combos;
print "$word: $possible possibilities\n";
foreach (@combos) {
print ' - ', join(' ', @$_), "\n";
}
print "\n";
}
sub Usage(){
return "$0 /path/to/dictionary /path/to/your_words";
}
Алгоритм Витерби намного быстрее. Он вычисляет те же результаты, что и рекурсивный поиск в ответе Дмитрия выше, но за O(n) раз. (Поиск Дмитрия занимает экспоненциальное время; Витерби делает это динамическим программированием.)
import re
from collections import Counter
def viterbi_segment(text):
probs, lasts = [1.0], [0]
for i in range(1, len(text) + 1):
prob_k, k = max((probs[j] * word_prob(text[j:i]), j)
for j in range(max(0, i - max_word_length), i))
probs.append(prob_k)
lasts.append(k)
words = []
i = len(text)
while 0 < i:
words.append(text[lasts[i]:i])
i = lasts[i]
words.reverse()
return words, probs[-1]
def word_prob(word): return dictionary[word] / total
def words(text): return re.findall('[a-z]+', text.lower())
dictionary = Counter(words(open('big.txt').read()))
max_word_length = max(map(len, dictionary))
total = float(sum(dictionary.values()))
Тестирование это:
>>> viterbi_segment('wickedweather')
(['wicked', 'weather'], 5.1518198982768158e-10)
>>> ' '.join(viterbi_segment('itseasyformetosplitlongruntogetherblocks')[0])
'its easy for me to split long run together blocks'
Чтобы быть практичным, вы, вероятно, захотите пару уточнений:
- Добавьте журналы вероятностей, не умножайте вероятности. Это позволяет избежать потери значения с плавающей точкой.
- Ваши входы, как правило, будут использовать слова, не входящие в ваш корпус. Этим подстрокам должна быть назначена ненулевая вероятность в виде слов, иначе у вас не будет решения или плохого решения. (Это так же верно для вышеупомянутого алгоритма экспоненциального поиска.) Эта вероятность должна быть откачана от вероятностей корпусных слов и правдоподобно распределена среди всех других слов-кандидатов: общая тема известна как сглаживание в статистических языковых моделях. (Тем не менее, вы можете избежать некоторых довольно грубых взломов.) Это - то, где алгоритм O(n) Витерби уничтожает алгоритм поиска, потому что рассмотрение не корпусных слов увеличивает фактор ветвления.
Pip install wordninja
>>> import wordninja
>>> wordninja.split('bettergood')
['better', 'good']
Лучший инструмент для работы здесь - это рекурсия, а не регулярные выражения. Основная идея состоит в том, чтобы начать с начала строки в поисках слова, затем взять оставшуюся часть строки и найти другое слово, и так далее, пока не будет достигнут конец строки. Рекурсивное решение является естественным, так как возврат должен происходить, когда заданный остаток строки не может быть разбит на набор слов. Приведенное ниже решение использует словарь, чтобы определить, что такое слово, и выводит решения по мере их нахождения (некоторые строки можно разбить на несколько возможных наборов слов, например, wickedweather может быть проанализирован как "злые мы на нее"). Если вам нужен только один набор слов, вам необходимо определить правила выбора наилучшего набора, возможно, выбрав решение с наименьшим количеством слов или установив минимальную длину слова.
#!/usr/bin/perl
use strict;
my $WORD_FILE = '/usr/share/dict/words'; #Change as needed
my %words; # Hash of words in dictionary
# Open dictionary, load words into hash
open(WORDS, $WORD_FILE) or die "Failed to open dictionary: $!\n";
while (<WORDS>) {
chomp;
$words{lc($_)} = 1;
}
close(WORDS);
# Read one line at a time from stdin, break into words
while (<>) {
chomp;
my @words;
find_words(lc($_));
}
sub find_words {
# Print every way $string can be parsed into whole words
my $string = shift;
my @words = @_;
my $length = length $string;
foreach my $i ( 1 .. $length ) {
my $word = substr $string, 0, $i;
my $remainder = substr $string, $i, $length - $i;
# Some dictionaries contain each letter as a word
next if ($i == 1 && ($word ne "a" && $word ne "i"));
if (defined($words{$word})) {
push @words, $word;
if ($remainder eq "") {
print join(' ', @words), "\n";
return;
} else {
find_words($remainder, @words);
}
pop @words;
}
}
return;
}
Я думаю, что вы правы, думая, что это не совсем работа для регулярного выражения. Я бы подошел к этому, используя идею словаря - ищите самый длинный префикс, который является словом в словаре. Когда вы найдете это, отрежьте его и сделайте то же самое с остальной частью строки.
Описанный выше метод подвержен неоднозначности, например, "drivereallyfast" сначала найдет "driver", а затем возникнет проблема с "eallyfast". Таким образом, вы также должны были бы откатиться назад, если бы столкнулись с этой ситуацией. Или, поскольку у вас не так много строк, которые нужно разделить, просто сделайте вручную те, которые потерпели неудачу в автоматическом разделении.
Так что я потратил около 2 дней на этот ответ, так как он мне нужен для моей собственной работы с НЛП. Мой ответ получен из ответа user27024 , который сам был получен из алгоритма Витерби. Я также абстрагировал его, чтобы взять каждое слово в сообщении, попытаться разбить его, а затем снова собрать сообщение. Я расширил код Дариуса, чтобы сделать его поддающимся отладке. Я также заменил «big.txt» и использовал wordfreq.библиотека вместо этого. В некоторых комментариях подчеркивается необходимость использования ненулевой частоты слов для несуществующих слов. Я обнаружил, что использование любой частоты выше нуля приведет к тому, что «iteasyformetosplitlongruntogetherblocks» не будет разделен на «itseasyformetosplitlongruntogetherblocks». Алгоритм в целом имеет тенденцию к чрезмерному или недостаточному разделению различных тестовых сообщений в зависимости от того, как вы комбинируете частоты слов и как вы обрабатываете пропущенные частоты слов. Я играл со многими настройками, пока он не стал вести себя хорошо. В моем решении для пропущенных слов используется частота 0,0. Он также добавляет вознаграждение за длину слова (в противном случае он имеет тенденцию разбивать слова на символы). Я перепробовал множество вознаграждений за длину, и мне кажется, что лучше всего для моих тестовых случаев работает
word_frequency * (e ** word_length). Были также комментарии, предостерегающие от умножения частоты слов вместе. Я попытался добавить их, используя среднее гармоническое и используя 1-частоту вместо формы 0,00001. Все они, как правило, превышали количество тестовых случаев. Простое перемножение частот слов работало лучше всего. Я оставил там свои операторы отладочной печати, чтобы другим было проще продолжать настройку. Наконец, есть особый случай, когда все ваше сообщение представляет собой слово, которого не существует, например «Slagle's», тогда функция разбивает слово на отдельные буквы. В моем случае я этого не хочу, поэтому у меня есть специальный оператор return в конце, чтобы вернуть исходное сообщение в таких случаях.
import numpy as np
from wordfreq import get_frequency_dict
word_prob = get_frequency_dict(lang='en', wordlist='large')
max_word_len = max(map(len, word_prob)) # 34
def viterbi_segment(text, debug=False):
probs, lasts = [1.0], [0]
for i in range(1, len(text) + 1):
new_probs = []
for j in range(max(0, i - max_word_len), i):
substring = text[j:i]
length_reward = np.exp(len(substring))
freq = word_prob.get(substring, 0) * length_reward
compounded_prob = probs[j] * freq
new_probs.append((compounded_prob, j))
if debug:
print(f'[{j}:{i}] = "{text[lasts[j]:j]} & {substring}" = ({probs[j]:.8f} & {freq:.8f}) = {compounded_prob:.8f}')
prob_k, k = max(new_probs) # max of a touple is the max across the first elements, which is the max of the compounded probabilities
probs.append(prob_k)
lasts.append(k)
if debug:
print(f'i = {i}, prob_k = {prob_k:.8f}, k = {k}, ({text[k:i]})\n')
# when text is a word that doesn't exist, the algorithm breaks it into individual letters.
# in that case, return the original word instead
if len(set(lasts)) == len(text):
return text
words = []
k = len(text)
while 0 < k:
word = text[lasts[k]:k]
words.append(word)
k = lasts[k]
words.reverse()
return ' '.join(words)
def split_message(message):
new_message = ' '.join(viterbi_segment(wordmash, debug=False) for wordmash in message.split())
return new_message
messages = [
'tosplit',
'split',
'driveourtrucks',
"Slagle's",
"Slagle's wickedweather liquidweather driveourtrucks gocompact slimprojector",
'itseasyformetosplitlongruntogetherblocks',
]
for message in messages:
print(f'{message}')
new_message = split_message(message)
print(f'{new_message}\n')
tosplit
to split
split
split
driveourtrucks
drive our trucks
Slagle's
Slagle's
Slagle's wickedweather liquidweather driveourtrucks gocompact slimprojector
Slagle's wicked weather liquid weather drive our trucks go compact slim projector
itseasyformetosplitlongruntogetherblocks
its easy for me to split long run together blocks
Это связано с проблемой, известной как разделение идентификатора или токенизация имени идентификатора. В случае ОП входные данные, по-видимому, являются связями обычных слов; при разделении идентификаторов входными данными являются имена классов, имена функций или другие идентификаторы из исходного кода, и проблема сложнее. Я понимаю, что это старый вопрос, и ОП либо решил их проблему, либо пошел дальше, но в случае, если кто-то еще сталкивался с этим вопросом при поиске сплиттеров идентификаторов (как я это делал не так давно), я хотел бы предложить Spiral (" Сплиттеры для Идентификаторов: Библиотека "). Он написан на Python, но поставляется с утилитой командной строки, которая может читать файл идентификаторов (по одному на строку) и разбивать каждый из них.
Разделение идентификаторов обманчиво сложно. Программисты обычно используют аббревиатуры, сокращения и фрагменты слов при именовании вещей, и они не всегда используют согласованные соглашения. Даже в тех случаях, когда идентификаторы действительно следуют некоторому соглашению, такому как случай верблюда, могут возникнуть неоднозначности.
В Spiral реализованы многочисленные алгоритмы разделения идентификаторов, в том числе новый алгоритм под названием Ronin. Он использует множество эвристических правил, английских словарей и таблиц частот токенов, полученных из хранилищ исходного кода майнинга. Ронин может разделять идентификаторы, которые не используют регистр верблюдов или другие соглашения об именах, включая такие случаи, как расщепление J2SEProjectTypeProfiler в [ J2SE, Project, Type, Profiler ], который требует от читателя J2SE как единое целое. Вот еще несколько примеров того, что может разделить Ронин:
# spiral mStartCData nonnegativedecimaltype getUtf8Octets GPSmodule savefileas nbrOfbugs
mStartCData: ['m', 'Start', 'C', 'Data']
nonnegativedecimaltype: ['nonnegative', 'decimal', 'type']
getUtf8Octets: ['get', 'Utf8', 'Octets']
GPSmodule: ['GPS', 'module']
savefileas: ['save', 'file', 'as']
nbrOfbugs: ['nbr', 'Of', 'bugs']
Используя примеры из вопроса ОП:
# spiral wickedweather liquidweather driveourtrucks gocompact slimprojector
wickedweather: ['wicked', 'weather']
liquidweather: ['liquid', 'weather']
driveourtrucks: ['driveourtrucks']
gocompact: ['go', 'compact']
slimprojector: ['slim', 'projector']
Как видите, он не идеален. Стоит отметить, что у Ronin есть ряд параметров, а их настройка позволяет разделить driveourtrucks тоже, но ценой ухудшения производительности программных идентификаторов.
Больше информации можно найти в репозитории GitHub для Spiral.
используйте Библиотеку чар. Лучший вариант. Посмотрите: https://www.youtube.com/watch?v=Q3UR-uBWGfY&amp;t=206s .
# Import the enchant library for spell-checking
import enchant
def split_merged_words(word_to_split):
splitted_words = []
dictionary = enchant.Dict("en_US")
word = word_to_split
length_of_word = len(word)
i = 0
while i < length_of_word:
for j in range(length_of_word, i, -1):
word_to_check = word[i:j]
if dictionary.check(word_to_check):
splitted_words.append(word_to_check)
i = j
break
return splitted_words
merged_words = input("Enter the merged words: ")
words = split_merged_words(merged_words)
print("The splitted words:", words)
Простое решение с Python: установите пакет wordsegment:pip install wordsegment.
$ echo thisisatest | python -m wordsegment
this is a test
Требуется решение на основе словаря. Это может быть несколько упрощено, если у вас есть ограниченный словарь слов, которые могут встречаться, в противном случае слова, которые образуют префикс других слов, будут проблемой.
Одно из решений может быть с рекурсией (то же самое можно преобразовать в динамическое программирование):
static List<String> wordBreak(
String input,
Set<String> dictionary
) {
List<List<String>> result = new ArrayList<>();
List<String> r = new ArrayList<>();
helper(input, dictionary, result, "", 0, new Stack<>());
for (List<String> strings : result) {
String s = String.join(" ", strings);
r.add(s);
}
return r;
}
static void helper(
final String input,
final Set<String> dictionary,
final List<List<String>> result,
String state,
int index,
Stack<String> stack
) {
if (index == input.length()) {
// add the last word
stack.push(state);
for (String s : stack) {
if (!dictionary.contains(s)) {
return;
}
}
result.add((List<String>) stack.clone());
return;
}
if (dictionary.contains(state)) {
// bifurcate
stack.push(state);
helper(input, dictionary, result, "" + input.charAt(index),
index + 1, stack);
String pop = stack.pop();
String s = stack.pop();
helper(input, dictionary, result, s + pop.charAt(0),
index + 1, stack);
}
else {
helper(input, dictionary, result, state + input.charAt(index),
index + 1, stack);
}
return;
}
Другое возможное решение - использование
Tries структура данных.
Ну, сама проблема не решаема только с помощью регулярного выражения. Решение (вероятно, не лучшее) состоит в том, чтобы получить словарь и сопоставить регулярное выражение для каждой работы в словаре с каждым словом в списке, добавляя пробел в случае успеха. Конечно, это не будет ужасно быстро, но это будет легко программировать и быстрее, чем ручная работа.
output :-
['better', 'good'] ['coffee', 'shop']
['coffee', 'shop']
pip install wordninja
import wordninja
n=wordninja.split('bettergood')
m=wordninja.split("coffeeshop")
print(n,m)
list=['hello','coffee','shop','better','good']
mat='coffeeshop'
expected=[]
for i in list:
if i in mat:
expected.append(i)
print(expected)
Это будет работать, если это camelCase. JavaScript!!!
function spinalCase(str) {
let lowercase = str.trim()
let regEx = /\W+|(?=[A-Z])|_/g
let result = lowercase.split(regEx).join("-").toLowerCase()
return result;
}
spinalCase("AllThe-small Things");
Существует пакет Python, выпущенный Santhosh thottingal, называемый mlmorph, который можно использовать для морфологического анализа.
https://pypi.org/project/mlmorph/
Примеры:
from mlmorph import Analyser
analyser = Analyser()
analyser.analyse("കേരളത്തിന്റെ")
дает
[('കേരളം<np><genitive>', 179)]
Он также написал блог на тему https://thottingal.in/blog/2017/11/26/towards-a-malayalam-morphology-analyser/
Я могу быть удручен за это, но пусть секретарь сделает это.
Вы потратите больше времени на решение для словаря, чем на ручную обработку. Кроме того, у вас не будет 100% уверенности в решении, поэтому вам все равно придется все равно уделить ему внимание.