Поиск существительных

Несколько геморройный, но качественный способ:
1. Берешь англ. словарь морфологии с aot.ru. Парсишь его (формат описан), получив на выходе список существительных во всех формах (там у каждой словоформы есть ряд атрибутов, в т.ч. часть речи).
2. Загоняешь все это в базу или хеш-контейнер. Самый быстрый вариант и, разумеется, самый требовательный по части памяти: создать на основе списка слов большой конечный автомат - тогда поиск по словарю всегда будет осуществляться с линейной относительно длины слова скоростью
3. PROFIT

>взять словарь существительных англ языка (думаю такой есть)

Части речи определяются и морфологическими признаками (если есть), и синтаксической ролью в предложении, и семантикой (если есть).

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

Задача изначальна некорректна.

Но, если решить нельзя, то решать можно :-)

Посмотри http://www.dict.org/ (или в репозитарии твоего дистра). Достаточно распарсить вывод dict, у существительных перед значениями стоит "n" , к сожалению в разных словарях вывод словарной статьи оформлен по-разному.

Например:

From The Collaborative International Dictionary of English v.0.48 [gcide]:

  Apple \Ap"ple\ ([a^]p"p'l), n. [OE. appel, eppel, AS. [ae]ppel,
     [ae]pl; akin to Fries. & D. appel, OHG, aphul, aphol, G.
     apfel, Icel. epli, Sw. [aum]ple, Dan. [ae]ble, Gael. ubhall,
     W. afal, Arm. aval, Lith. ob[*u]lys, Russ. iabloko; of
     unknown origin.]
     1. The fleshy pome or fruit of a rosaceous tree ({Pyrus
        malus}) cultivated in numberless varieties in the
        temperate zones.
        [1913 Webster]
.....

т.е. некоторая шапка, потом само слово, произношение, часть речи ("n.") происхождение, и далее список значений, какие вообще есть.

> создать на основе списка слов большой конечный автомат - тогда поиск по словарю всегда будет осуществляться с линейной относительно длины слова скоростью

Сопоставление со списком делается тоже за линейное время. Автомат ещё надо измудриться хранить как-то так, чтобы не сильно много памяти жрал и при этом по нему можно было быстро ползать.

Есть замечательная книженция Гасфилда "Строки, деревья и последовательности в алгоритмах". Там можно найти способы быстро решать подобные задачки: сопоставление с множеством шаблонов.

А можно воспользоваться СУБД с поддержкой специальных текстовых индексов. Или поискать какую-нибудь либу, которая умеет хранить переваренное в файле, чтоб не городить много.

Всем спасибо, буду пробовать!

> Сопоставление со списком делается тоже за линейное время

Это как?

> Автомат ещё надо измудриться хранить как-то так, чтобы не сильно много памяти жрал...

У топикстартера простая задача: определение только части речи по слову. Соответственно, если замутить минимальный конечный автомат, памяти он будет жрать не так уж и много, в сравнении с большим хешем. Например, конечный автомат для слов
"стол"
"пол"
"пи***бол"
начиная с буквы "о" проходят одинаковые состояния

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

> Чот автомат помойму будет сильно большим

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

> замучаюсь перебирать

Ты же его не карандашом в тетради строить будешь

> слова английские

На английском словаре от aot генерится примерно 200000 корректных словоформ (для всех частей речи) - это совсем немного. В этом случае можно вполне обойтись хеш-таблицей. Для сравнения русский словарь генерит около 6000000 словоформ.
Только, как уже писали, с английским языком у тебя достаточно остро возникает проблема с соотнесением того или иного слова к части речи. Синтаксический анализатор, к слову, на aot тоже есть - с иходниками.

Ок, спасибо за направление куда копать, бум копать;)

>> Сопоставление со списком делается тоже за линейное время

> Это как?

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

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

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

Есть идея по мотивам автомата, но несколько упрощённая. Похожа ещё на арифметические деревья. База данных представляет собой массив блоков. Каждый блок состоит из N чисел (N=26 по числу букв в алфавите). Скажем, 0 означает, что здесь слово закончилось, -1 - зашли в тупик, другое число - номер следующего блока. Берём первый блок из файла и подставляем по очереди буквы из слова. 100000 слов со средней длиной 5 букв сожрут порядка полсотни мегов.

>Есть идея по мотивам автомата, но несколько упрощённая. Похожа ещё на арифметические деревья. База данных представляет собой массив блоков. Каждый блок состоит из N чисел (N=26 по числу букв в алфавите). Скажем, 0 означает, что здесь слово закончилось, -1 - зашли в тупик, другое число - номер следующего блока. Берём первый блок из файла и подставляем по очереди буквы из слова. 100000 слов со средней длиной 5 букв сожрут порядка полсотни мегов.
Если честно не очень понял, можно чуть подробнее?

> С автоматом аналогично, но всё-таки не настолько ужасно.

Сарказм?

> Вряд ли оптимизация автомата сильно улучшит положение дел

http://aot.ru/docs/sokirko/Dialog2004.htm
Ъ-version:

Язык        Размер автомата    Размер автомата и морф. инф.
русский     4,7 Мб             9 Мб
английский  1 Мб               3 Мб
Пропускная способность для русского языка - 360 тыс. слов в сек.

> Есть идея по мотивам автомата, но несколько упрощённая...
Ты как раз описал типичную реализацию КА для обработки строк. Осталось только сделать его минимальным и оптимизнуть :)

Как на автомате можно построить проверку на существительное?
Я знаю как сделать конечный автомат на проверку конкретного слова. Знаю как сделать сделать автомат для бесконечной после-ти с повторяющимися блоками. Но что объединяет существительные?
С АОТ скачал вроде как словарь(морфологический), потыкал за 5 минут не разобрался, буду смотреть завтра днем чо и как. (http://aot.ru/download/eng-src-morph.tar.gz)
П.С. сделать всмысле написать на бумажке\нарисовать на бумажке. Ни разу реализацию автомата не делал на ЯП.

> Пропускная способность для русского языка - 360 тыс. слов в сек.

Правда упоминаний о системе, на которой проводился этот бенчмарк я там не нашел. Но это понятно, лингвисты, х**ле...

> Как на автомате можно построить проверку на существительное?

Судя по описанию задачи, тебя интересует только проверка на существительные - это аналогично обычной проверке на наличие слова в словаре, содержащем только существительные. Повторюсь, в рамках твоей задачи тебе нет смысла запариваться с КА - достаточно будет затолкать все нужные слова в хеш. У английского языка очень ограниченная морфология.

Ну с запихивание слов в словарь и проверки каждого слова по не нему я понял, но расскажите как с КА, а то чот интересно стало:)

> ...но расскажите как с КА, а то чот интересно стало:)

Это та же самая проверка по словарю, только словарь хранится в виде КА, что позволяет обеспечить оптимальную производительность.

Подробности применительно к обработке слов естественного языка можно узнать, например, здесь http://www.eti.pg.gda.pl/~jandac/incr_fst.ps.gz

Ок, спасибо, буду смотреть.

wordnet еще посмотри