Поиск словарных слов

Я не уверен, сколько времени или частоты вы должны делать это (это разовая операция? ежедневно? еженедельно?), но вам, очевидно, понадобится быстрый взвешенный поиск по словарю.

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

Я бы посмотрел на Попытки. Используя один из них, вы сможете эффективно находить (и взвешивать) свои префиксы, именно то, что вам нужно.

Вам придется самостоятельно создавать попытки из хорошего источника словаря и взвешивать узлы на полных словах, чтобы обеспечить себе механизм хорошего качества для ссылок.

Здесь просто мозговой штурм, но если вы знаете, что ваш набор данных состоит в основном из дуплетов или триплетов, вы, вероятно, могли бы обойтись несколькими поисками Trie, например, найти «Spic», а затем «ejet», а затем обнаружить, что оба результата имеют низкий балл, отказаться от «Spice» и «Jet», где обе попытки дадут хороший комбинированный результат между ними.

Также я бы рассмотрел возможность использования частотного анализа наиболее распространенных префиксов до произвольного или динамического предела, например. фильтрация «the», «un» или «in» и взвешивание их соответственно.

Звучит как забавная задача, удачи!

Если цель состоит в том, чтобы найти «максимально возможный разрыв для входных данных», как вы ответили, то алгоритм может быть довольно простым, если вы используете некоторую теорию графов. Вы берете составное слово и строите граф с вершинами до и после каждой буквы. У вас будет вершина для каждого индекса в строке и одна за концом. Затем вы найдете в своем словаре все допустимые слова, которые являются подстроками сложного слова. Затем для каждой допустимой подстроки добавьте к графу ребро с весом 1, соединяющее вершину перед первой буквой в подстроке с вершиной после последней буквы в подстроке. Наконец, используйте алгоритм кратчайшего пути, чтобы найти путь с наименьшим количеством ребер между первой и последней вершиной.

Псевдокод примерно такой:

parseWords(compoundWord)
    # Make the graph
    graph = makeGraph()
    N = compoundWord.length
    for index = 0 to N
        graph.addVertex(i)

    # Add the edges for each word
    for index = 0 to N - 1
        for length = 1 to min(N - index, MAX_WORD_LENGTH)
            potentialWord = compoundWord.substr(index, length)
            if dictionary.isElement(potentialWord)
                graph.addEdge(index, index + length, 1)

    # Now find a list of edges which define the shortest path
    edges = graph.shortestPath(0, N)

    # Change these edges back into words.
    result = makeList()
    for e in edges
        result.add(compoundWord.substr(e.start, e.stop - e.start + 1))
    return result

Я, конечно, не тестировал этот псевдокод, и могут быть какие-то ошибки индексации, и нет никакой проверки ошибок, но основная идея есть. Я делал что-то подобное в школе, и это работало очень хорошо. Циклы создания ребер — это O(M * N), где N — длина составного слова, а M — максимальная длина слова в вашем словаре или N (в зависимости от того, что меньше). Время выполнения алгоритма кратчайшего пути будет зависеть от того, какой алгоритм вы выберете. На ум сразу приходит Дейкстры. Я думаю, что его время выполнения составляет O (N ^ 2 * log (N)), поскольку максимально возможное количество ребер составляет N ^ 2.

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

И как вы будете решать, как делить вещи? Посмотрите в Интернете, и вы найдете примеры URL-адресов, которые, как оказалось, имеют другое значение.

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

PenIsland
KidsExchange
TherapistFinder

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

Итак, данное слово является составным словом, состоящим из двух других английских слов? У вас может быть какая-то таблица поиска для всех таких составных слов, но если вы просто проверите кандидатов и попытаетесь сопоставить их с английскими словами, вы получите ложные срабатывания.

Изменить: похоже, мне придется пойти, чтобы привести несколько примеров. Слова, о которых я думал, включают:

accustomednesses != accustomed + nesses
adulthoods != adult + hoods
agreeabilities != agree + abilities
willingest != will + ingest
windlasses != wind + lasses
withstanding != with + standing
yourselves != yours + elves
zoomorphic != zoom + orphic
ambassadorships != ambassador + ships
allotropes != allot + ropes

Вот некоторый код Python, который можно попробовать, чтобы понять суть. Получите словарь на диске и попробуйте:

from __future__ import with_statement

def opendict(dictionary=r"g:\words\words(3).txt"):
    with open(dictionary, "r") as f:
        return set(line.strip() for line in f)

if __name__ == '__main__':
    s = opendict()
    for word in sorted(s):
        if len(word) >= 10:
            for i in range(4, len(word)-4):
                left, right = word[:i], word[i:]
                if (left in s) and (right in s):
                    if right not in ('nesses', ):
                        print word, left, right

Мне кажется, что вы хотите хранить свой словарь в Trie или в структуре данных DAWG.

Trie уже хранит слова как составные слова. Таким образом, "spicejet" будет храниться как "spicejet", где * означает конец слова. Все, что вам нужно сделать, это найти составное слово в словаре и отслеживать, сколько терминаторов конца слова вы нажали. Оттуда вам нужно будет попробовать каждую подстроку (в этом примере мы еще не знаем, является ли «jet» словом, поэтому нам придется искать это).

Мне приходит в голову, что существует относительно небольшое количество подстрок (минимальная длина 2) из ​​любого разумного составного слова. Например, для "spicejet" я получаю:

'sp', 'pi', 'ic', 'ce', 'ej', 'je', 'et',
'spi', 'pic', 'ice', 'cej', 'eje', 'jet',
'spic', 'pice', 'icej', 'ceje', 'ejet',
'spice', 'picej', 'iceje', 'cejet',
'spicej', 'piceje', 'icejet',
'spiceje' 'picejet'

... 26 подстрок.

Итак, найдите функцию для генерации всех этих (скользите по строке, используя шаги 2, 3, 4... (len(yourstring) - 1), а затем просто проверяйте каждый из них в наборе или хеш-таблице.

Недавно был задан аналогичный вопрос: алгоритм разделения слов. Если вы хотите ограничить количество разбиений, вы должны отслеживать количество разбиений в каждом из кортежей (так что вместо пары будет тройка).

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

# python-ish pseudocode
def splitword(word):
    # word is a character array indexed from 0..n-1

    for i from 1 to n-1:
        head = word[:i]  # first i characters
        tail = word[i:]  # everything else

        if is_word(head):
            if i == n-1:
                return [head]   # this was the only valid word; return it as a 1-element list
            else:
                rest = splitword(tail)
                if rest != []:   # check whether we successfully split the tail into words
                    return [head] + rest

    return []  # No successful split found, and 'word' is not a word.

По сути, просто попробуйте разные точки останова, чтобы увидеть, сможем ли мы составить слова. Рекурсия означает, что он будет возвращаться назад до тех пор, пока не будет найдено успешное разделение.

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

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

Именно с этой проблемой мы сталкиваемся в химии, где имена состоят из конкатенации морфем. Пример:

ethylmethylketone

где морфемы:

ethyl methyl and ketone

Мы решаем это с помощью автоматов и максимальной энтропии, а код доступен на Sourceforge.

http://www.sf.net/projects/oscar3-chem

но имейте в виду, что это потребует некоторой работы.

Иногда мы сталкиваемся с двусмысленностью и все еще находим хороший способ сообщить об этом.

Чтобы провести различие между penIsland и penisLand, потребуется эвристика, специфичная для предметной области. Вероятная интерпретация будет зависеть от используемого корпуса — ни одна лингвистическая проблема не зависит от анализируемой области или областей.

В качестве другого примера строка

weeknight

можно разобрать как

wee knight

or

week night

Оба «правы» в том, что подчиняются форме «прилагательное-существительное» или «существительное-существительное». И то, и другое имеет смысл, и то, что будет выбрано, будет зависеть от области использования. В фэнтезийной игре более вероятно первое, а в коммерческой — второе. Если у вас есть проблемы такого рода, будет полезно иметь корпус согласованного использования, который был аннотирован экспертами (технически «Золотой стандарт» в обработке естественного языка).

Я бы использовал следующий алгоритм.

1. Начните с отсортированного списка слов для разделения и отсортированного списка отклоненных слов (словарь).

2. Создайте результирующий список объектов, которые должны хранить: оставшееся слово и список совпадающих слов.

3. Заполните список результатов словами, которые нужно разделить как оставшиеся слова.

4. Пройдитесь по массиву результатов и словарю одновременно, всегда увеличивая наименьшее из двух, аналогично алгоритму слияния. Таким образом, вы можете сравнить все возможные совпадающие пары за один проход.

5. Каждый раз, когда вы находите совпадение, т. е. слово из разделенных слов, которое начинается со словарного слова, замените совпадающее словарное слово и оставшуюся часть в списке результатов. Вы должны принять во внимание возможные кратные.

6. Каждый раз, когда оставшаяся часть пуста, вы нашли окончательный результат.

7. Каждый раз, когда вы не находите совпадения на «левой стороне», другими словами, каждый раз, когда вы увеличиваете указатель результата из-за отсутствия совпадения, удаляйте соответствующий элемент результата. Это слово не имеет соответствий и не может быть разделено.

8. Как только вы доберетесь до конца списков, у вас будет список частичных результатов. Повторяйте цикл, пока он не станет пустым — перейдите к пункту 4.