Алгоритм разделения слов

Question

Что это за алгоритм, который, по-видимому, используется на страницах парковки доменов, который берет незаполненную группу слов (например, «thecarrotofcuriosity») и более или менее правильно разбивает его на составляющие слова (например, «морковь любопытства» ")?

Answer 1

Начните с базовой Trie структуры данных, представляющей ваш словарь. Когда вы выполняете итерацию по символам строки, ищите свой путь по дереву с помощью набора указателей, а не одного указателя - набор засеян корнем дерева. Для каждой буквы весь набор продвигается сразу через указатель, обозначенный буквой, и, если элемент набора не может быть продвинут перед буквой, он удаляется из набора. Всякий раз, когда вы достигнете возможного конца слова, добавьте новый корень слова в набор (отслеживая список слов, связанных с этим элементом набора). Наконец, после того, как все символы были обработаны, вернуть произвольный список слов, который находится в корне дерева. Если их несколько, это означает, что строку можно разбить несколькими способами (например, «therapistforum», который можно проанализировать как [«therapist», «forum»] или [«the», «насильник», «форум»). ]) и он не определен, который мы вернем.

Или в неработающем псевдокоде (Java foreach, кортеж, обозначенный паренами, набор, обозначенный фигурными скобками, cons using head :: tail, [] пустой список):

List<String> breakUp(String str, Trie root) {
    Set<(List<String>, Trie)> set = {([], root)};
    for (char c : str) {
        Set<(List<String>, Trie)> newSet = {};
        for (List<String> ls, Trie t : set) {
            Trie tNext = t.follow(c);
            if (tNext != null) {
                newSet.add((ls, tNext));
                if (tNext.isWord()) {
                    newSet.add((t.follow(c).getWord() :: ls, root));
                }
            }
        }
        set = newSet;
     }
     for (List<String> ls, Trie t : set) {
        if (t == root) return ls;
     }
     return null;
 }

Дайте мне знать, если мне нужно уточнить или я что-то пропустил ...

Answer 2

Я полагаю, что они берут список словарных слов, например /usr/share/dict/words, в вашей обычной системе Unix или садовой разновидности и пытаются найти наборы совпадений слов (начиная слева?), В результате которых покрывается наибольшее количество исходного текста по совпадению. Простая реализация поиска в ширину, вероятно, будет работать нормально, поскольку она, очевидно, не должна работать быстро.

Answer 3

(отказ от ответственности: я сам не пробовал, так что принимайте это просто как пищу для экспериментов. 4 грамма в основном берутся из голубого неба, просто из моего опыта, что 3 грамма не будут работать слишком хорошо ; 5 граммов и более могут работать лучше, даже если вам придется иметь дело с довольно большим столом). Это также упрощенно в том смысле, что в нем не учитывается окончание строки - если это работает для вас иначе, вам, вероятно, придется подумать об исправлении окончаний.

Этот алгоритм будет работать в предсказуемое время, пропорциональное длине строки, которую вы пытаетесь разделить.

Итак, сначала: возьмите много читабельных текстов. для каждого текста, предполагая, что он находится в одной строке str , запустите следующий алгоритм (псевдокод-нотация, предполагается, что [] является индексацией, подобной хеш-таблице, и что несуществующие индексы возвращают '0' ):

for(i=0;i<length(s)-5;i++) {
  // take 4-character substring starting at position i
  subs2 = substring(str, i, 4); 
  if(has_space(subs2)) {
    subs = substring(str, i, 5);
    delete_space(subs);
    yes_space[subs][position(space, subs2)]++;
  } else {
    subs = subs2;
    no_space[subs]++;
  }
}

Это создаст вам таблицы, которые помогут решить, нужно ли в данном 4-грамме вставлять пробел или нет.

Затем возьмите вашу строку для разделения, я обозначу ее как xstr и сделайте:

for(i=0;i<length(xstr)-5;i++) {
  subs = substring(xstr, i, 4);
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] -= no_space[subs];
  }
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] += yes_space[subs][j];
  }
}

Затем вы можете пройтись по массиву " do_insert_space_here []" - если элемент в данной позиции больше 0, то вы должны вставить пробел в этой позиции в исходной строке. Если оно меньше нуля, то не стоит.

Пожалуйста, напишите здесь, если вы пытаетесь (или что-то в этом роде), и это работает (или не работает) для вас: -)

Answer 4

Я представляю, как эти сайты делают это так:

1. Получить список слов для вашего целевого языка
2. Удалите "бесполезные" слова, такие как "a", "the", ...
3. Пробежаться по списку и проверить, какие слова являются подстрока имени домена
4. Возьмите самые распространенные слова из оставшегося списка (или те, которые имеют самый высокий рейтинг AdSense, ...)

Конечно, это приводит к бессмысленному обмену экспертами, но что еще можно ожидать там ...