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

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

4 ответа

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

Или, в разбитом псевдокоде (Java foreach, кортеж, обозначенный символами parens, установленный с помощью фигурных скобок, cons, используя 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;
 }
</string></string></string></string></string>

Сообщите мне, если мне нужно уточнить или я что-то пропустил...


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


Я хотел бы, чтобы эти сайты делали это схоже с этим:

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

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


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

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

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

for(i=0;i
<p>Это создаст вам таблицы, которые помогут решить, должен ли данный 4-граммовый шрифт иметь место в нем, вставленное или нет.</p> <p>Затем возьмем вашу строку для разделения, я обозначаю ее как xstr и делаю:</p> <pre class="prettyprint linenums">for(i=0;i</pre><code> <p>Затем вы можете пройти массив "do_insert_space_here []", если элемент в заданной позиции больше 0, тогда вы должны вставить пробел в эту позицию в исходной строке. Если это меньше нуля, тогда вы не должны.</p> <p>Пожалуйста, напишите примечание здесь, если вы попробуете (или что-то в этом роде), и он работает (или не работает) для вас: -)</p>

licensed under cc by-sa 3.0 with attribution.