Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Май 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор
Калашников О.А.

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Алгоритмы и теория программирования


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Роман Селиверстов
Статус: Советник
Рейтинг: 4633
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2478
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 2332
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска:158
Дата выхода:08.05.2012, 13:30
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:172 / 84
Вопросов / ответов:1 / 2

Консультация # 185967: Здравствуйте уважаемые эксперты! У меня возникли сложности с таким вопросом:

Тест Егорова на способность системы к обобщениям и поиску закономерностей.
Постановку задачи мы сделаем максимально неформальной, чтобы был понятен больше ее смысл, чем описанные ограничения. Существует естественно-языковый текст. ...

Консультация # 185967:

Здравствуйте уважаемые эксперты! У меня возникли сложности с таким вопросом:

Тест Егорова на способность системы к обобщениям и поиску закономерностей.

Постановку задачи мы сделаем максимально неформальной, чтобы был понятен больше ее смысл, чем описанные ограничения.
Существует естественно-языковый текст. (Например, первые семь страниц романа Толстого "Анна Каренина".)
Существует система, на вход которой мы подаем этот текст как последовательность символов. При этом у нас нет каких-то заранее выделенных символов, система не имеет представление о том, что "пробел" и "запятая" - это служебные символы, один разделяет слова, другой предназначен для пунктуации. Будем считать, что символ - это просто некоторый идентификатор, например, байт.
Система может иметь представление о том, что символ (байт) на входе - это экземпляр такого понятия как "символ", т.е. система может иметь "базу знаний", в которой будет существовать такой экземпляр как "символ", который как-то специфицирован, например, по своему байтовому значению. (Тогда "пробел" будет иметь ID = 32.)
Задача: Найти такие архитектуру системы, механизмы, методы обработки этого массива, чтобы система самостоятельно, без дополнительного обучения сгенерировало понятие "слово", специфицировало его и выделила все слова в исходном тексте.
Разрешается: Вводить в систему любые правила обработки, предположения об устройстве мира и эволюции, собирать статистическую и прочую информацию с исходного текста и заниматься прочей работой.
Запрещается: В явном или неявном виде задавать понятие "слово" (например, предполагать до обработки, что слово - это последовательность символов между пробелами или идти на другие "ухищрения"), иметь в "базе знаний" какие-то частные правила выделения объектов, получать информацию в систему, кроме исходного тек ста (например, диалог с оператором, толковый словарь и т.п.).
Заранее спасибо за помощь!

Дата отправки: 05.05.2012, 13:15
Вопрос задал: Куценко Андрей Валерьевич (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Vest (Студент):

Здравствуйте, Андрей Валерьевич!

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

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

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

На основе статистики выбрать первые несколько символов, которые наиболее часто употребляются в тексте. И предположить, что текущий символ является разделителем (р). Для них осуществить поиск по шаблону: "рхр", "рххр". Эти правила определяют, что разделитель как минимум отделяет один или два л юбых символа от остальных. Можно было бы воспользоваться правилом, где три любых символа идут подряд, но это если возникнет противоречивая ситуация.
Отдельно, можно предположить, что разделитель не будет присутствовать в начале или конце текста (или строки). Потому что в задаче ничего не говорится про разрыв строк, и мы можем предположить, что строки непрерывны и отделяются друг от друга клавишами Enter.

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

Другие правила, которые предлож ил Алексей на форуме позволят помочь вам узнать цифры или специальные символы. Но опять же, надо смотреть на живом примере и экспериментировать.

Консультировал: Vest (Студент)
Дата отправки: 05.05.2012, 18:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Алексей Бурин (3-й класс):

Здравствуйте, Куценко Андрей Валерьевич!

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

(1) подсчёт символов
(1.2) выбор 3-х групп символов
1 - вероятные разделители
2 - вероятные буквы
3 - вероятные специальные символы
* группы должны иметь довольно существенную разницу, например
вес разделителя 100 -90 %
вес буквы 70 - 30 %
вес знака 10-1 % (знак в данном случае - знак препинания или служебный символ)
тут считаешь сколько раз встречается каждый символ и самый большой результат берёшь за 100%
** естественно, может получится несколько символов в группе 1.
в таком случае, если например, в первой группе оказалось 3 символа - каждый из них является разделителем с вероятностью в 33%
***статистику и распределение по группам не выбрасывай - сделай табличку со всеми найденными с имволами и занеси туда статистику для каждого
(2) уточнить разделитель
в случае, если в группе 1 оказалось несколько символов, нужно отсеять "лишние" (например ' ', о, а)
тут нужно применять правила.. можно придумать кучу правил.
правило 1 - длина слов. смысл в том, что знаки препинания делят цепочки символов на более мелкие слова, чем буквы
нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя.
причём, мы ищем "статистически" - то есть лучше выбрать не одно а 10 самых длинных "слов" и взять их среднюю длину.
например текст "нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя."
даст результат "пробел" - самое длинное слово - 13 символов, 'о' - 46 символов, 'а' - 24 символа.
то есть "о" - 100%, "а" - 52% и пробел - 28%.
разница очевидна.
правило 2 - знаки всегда идут до или после пробела.
тоже хорошее правило... но пока что невозможно быть уверенным на счёт знаков, то есть пробел никогда не будет стоять рядом с "ъ"
с другой стороны, ни "а" ни "о" тоже не стоят рядом с "ъ", что делает это правило оправданным.
нужно считать пары "знак"+"пробел" или "пробел"+"знак" для всех возможных пробелов со всеми возможными знаками
например, тот же текст " нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя. "
для пробела даст 5 совпадений ( ","+" "), ( "ь"+" " ), ("." + " ")
для "о" даст 1 совпадение ("о" + ",")
для "а" даст 0 совпадений
я в этом случае указал и "ь" потому что скорее всего буквы "ь", "ъ" ока жутся в группе знаков..
в любом случае - правило однозначно работает
...можно составить сколько угодно правил..
в итоге, используя набор правил можно выбрать наиболее вероятный разделитель
*я рекомендую ВСЕ результаты сохранять в табличке, в которой записана статистика по символам
в разных столбцах, конечно ))

(3) уточнить знаки (знаки препинания и специальные символы)
нужно применить другой набор правил к тексту
например
правило 1 знаки - это символы, которые всегда идут до или после "разделителя"
берёшь список всех символов, которые встретились в тексте и начинаешь просматривать текст
если встречается сочетание "символ"+"пробел" или "пробел"+"символ" - подтверждаешь этот символ
если встречается сочетание "не пробел"+"символ"+"не пробел" - вычёркиваешь этот символ из списка.
получается список из "вычеркнутых", "подтверждённых" ; и "не подтверждённых" знаков - заносим в ту же табличку со статистикой
"подтверждённые знаки", которые входят в г руппу 3 - можно считать доказанными
"вычеркнутые знаки" - это буквы типа "ъ"
"не подтверждённых" теоретически быть не должно... если появятся - стоит поискать ошибки

(4) Правила - "заглавные буквы"
можно применить правило поиска "заглавных букв" по шаблону типа
"пробел"+"возможная заглавная буква"+"буква"
бывают одиночные заглавные буквы ( "А", "И"), но их невозможно подтвердить..
подтверждение "заглавных букв" - считать "слово" после "заглавной буквы" и найти совпадение в тексте
если найдётся совпадение, но вместо заглавной буквы будет стоять другая буква - можно считать "заглавную букву" доказанной
и даже занести её в ту же табличку на против соответствующей "строчной буквы"
если одной "заглавной букве" будет соответствовать несколько "строчных букв" то нужно считат ь, что это исключение
- вычеркнуть символ из списка "заглавных букв" и не применять к нему это правило.
если есть несколько исключений, то можно считать, что это правило не работает на данном тексте.


(5) Дополнительные правила - "цифры" это сложный разбор текста...
"цифры" могут входить во все 3 группы, но практически всегда идут вместе друг с другом
это работа для небольшой базу данных...
нужно прочитать текст и сделать табличку из всех сочетаний всех символов, которые встречаются в тексте,
подсчитав количество таких сочетаний.
при разборе нужно принять во внимание, что, например, "б" скорее всего никогда не встретится с "щ" но оба символа встретятся с "о"
тут можно использовать порог, например "цифра с 80% вероятностью"
но, нужно помнить, что требуется проанализировать БОЛЬШОЙ объём текста
и всё равно - не факт, что удастся корректно выделить "цифры"

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

smile

Консультировал: Алексей Бурин (3-й класс)
Дата отправки: 08.05.2012, 07:50
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное