Естьли готовые алгоритмы что можно без всяких словарей узнать что word это нормальное слово а kdjghd это просто набор букв??

Ну в том виде в котором ты привёл, достаточно просто поискать в слове гласные 

А в общем случае ответ нет. Нельзя. Можно конечно насобирать кучу правил слообразования и характерных конструкций. Но язык ведь живая система и если даже сегодня ты учтёшь 90% случаев, на завтра появится ещё несколько не отвечающих никаким правилам. 

Это сообщение отредактировал(а) W4FhLF - 12.5.2007, 11:43

Не полностью согласен с W4FhLF.
Вероятность определения слово или не слово будет не 100%, но всеже высокая. На этом принципе работают авто переключатели клавиатуры.
принцип римерно такой: на основе словаря создается база слогов которые встречаются (присущи) в данном языке, а также база сопоставлений слогов.
В результате получаем систему распознавания слов + примитивную проверку орфографии. ;)

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

W4FhLF. прав на 100%, как он и сказал В ОБЩЕМ СЛУЧАЕ задаче не решаема. А вы взяли и сослались на частность

esperant0, 

в вопросе было "без словарей". Пожалуйста, укажите, где в моем посте затронуты частности.



не совсем понял "эффективность"? это что, скорость или вероятность правильного распознавания?
При использовании словаря скорость обработки будет очень маленькая, даже при условии структурирования словаря. + в словарь врядли можно занести все возможные словоформы, а вот для метода связанных слогов это не проблема + в слоговом словаре будет порядка 1000 записей и до 500 слоговых связок, что обеспечивает значительный выигрыш в скорости.
Использование даже самого навороченного словаря будет менее эффективно чем простенького семантического анализатора. Не обязательно знать все слова, достаточно знать как они формируются в языке.

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

Добавлено через 2 минуты и 45 секунд
Насчёт скорости ты не прав... Поюзай хотя бы тот же lingvo в offline версии, там число словоформ стремиться к миллиону наверное и поиск осуществялется моментально. 

Среднее ожидаемое время O(lg(lg(n)))
При мильиярде слов - всего 5 итераций. Помойму это совсем немного.
Вот тока где памяти взять на такое количество слов...

А как быть со словом "Мкртчан" (фамилия актёра)? Оно попадает под правила словообразования? По-моему нет. Так что без словаря врядли. Как человек распознает слова? Он их просто помнит, а не пытается подогнать под правила. Вот и ответ. 

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

Lomir, не совсем понял откуда происходит ваша формула сложности. (вывод, предпосылки). Теоретически (на мой взгляд) она близка к истине если под итерацией понимать полный цикл поиска одной буквы. Но насколько мне известно сложность поиска в упорядоченном графе равна О(n) где n - глубина графа.
Если Вас известен алгоритм реализующий O(lg(lg(n))) то пожалуйста представте его как доказательство.


Таких слов не много и для них можно построить пользоватетьский набор правил, в данном случае это один слог. Я не уверен, что эта фамилия будет в словаре + фамилия не русская.

Добавлено через 9 минут и 14 секунд

В словаре Ожогова 53 тыс слов, Даля - ~70 тыс, Орфографический словарь русского языка 106тыс. Милиона нигде нет.
А у лингво как раз применяется симантические правила: слова ищется по корню, а далее его словоформа.
Никогда не задавался вопросом: почему лингво столько весит? Поиск ведется не по словарю, а по специальным структурированным индексам, но это память.

Добавлено через 14 минут и 16 секунд
Вобщем то выбор метода зависит от цели. 
Но в любом случае использование словаря не позволит учесть все словоформы (падежи, склонения, времена, числа).

Не слов конечно, это просто я неправильно выразился, в моей версии 1.5 миллиона словарных статей. 
Ясное дело, что поиск происходит по корню, но суть одна, работа идёт со словарём. Lingvo работает со словарём очень быстро - это факт. И факт этот говорит о том, что утверждение:

Неверно  

Сколько весит? Сама программа весит 17 Мб. Словарь - 100 мб и озвучка 100 мегабайт. 




Это ты только что подсчитал?

Добавлено через 2 минуты и 31 секунду


Английский совсем другой язык и там со всем этим гораздо проще. А по сабжу, я так понял, именно English и нужен. 

Сарказм не понятен. Внимательно читай написанное и математика не пригодится.


ну и сколько кб на одно слово?


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


А я не понял   

Тогда мне непонятен сарказм в отношении Bitter'a. Ибо он был абсолютно прав, если человек не знает слова, то он может только сказать насколько корректно оно составлено, поэтому я и говорю, что при простом анализе словообразования будет слишком много ложных срабатываний и пока мы не знаем конечную цель данной задачи мы не можем утверждать, что эффективней, вот и всё. 



Ну если учитывать, что одно слово иногда имеет 50 значений(чаще около 7 в среднем) + Объяснения терминов и общепринятых сокращений + связи(синонимы, антонимы) и многое другое. Вот учитывая, что это всё хранится в одной базе, не так-то много получается. 



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

Добавлено через 32 секунды

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