| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > статистический анализ |
| Автор: shara 30.3.2009, 18:14 |
| В общем столкнулся с задачей после определенного преобразования (чего скрывать, после дешифрования текста) хочу программно определить читаемость получившегося открытого(расшифрованного) текста. каких-то однозначных слов признаков (типо MS-WORD и т.д.) в тексте нет. известно только что он изначально читаемый. у меня в наличии имеется большая база схожих текстов, тоесть есть на чем насчитать статистику - биграмы, четрехграммы. Собаственно вопрос, хочу разработать алгоритм который имея в наличии статистику множества читаемых открытых текстов определял читаемость заданного дешифрованного сообщения. З.Ы. знаком с теорией и практикой нейронных сетей, считаю что с их использванием можно решить данную задачу, но не хочу их применять в силу "ненаучности" подхода. как самый крайний случай |
| Автор: aleksh 30.3.2009, 23:57 |
| а как такой вариант -- запускасть в ворд и там пускать проверку на орфографию? если конкретно по статистике -- можно из открытых тескстов сформировать словари сгруппированные по количесву букв или заглавной букве, потом в дешефрированном тексте брать слова по очереди и проверять вхождение в словарь. после некоторого количества прогонок можно будет найти оптимальное количество "не попавших" слов для признания текста читаемым. но тут проблема -- рода и падежи, морфология родной речи в общем, хотя это тоже решаемо. вот как-то так, если заинтересовало, можно обдумать детальней |
| Автор: v2v 31.3.2009, 00:12 | ||
вот их и считай. возьми "Войну и Мир" , собери статистику по 5ти самых популярных и самых не популрярных : - букв - биграм и их и проверяй на наличие в первой , последней пятерке в своём текст. правда для чистоты эксперимента текст надо предварительно обработать - переделать в одно большое слово, тоесть выбросить все пробелы и знаки препинания. |
| Автор: shara 31.3.2009, 00:18 | ||
aleksh,
не подходит потому что вся суть данной идеи чтобы проверка работала автоматически и программа сама делала вывод насчет читаемости текста без участия человека идея со словарем тоже не приемлема, я сам раньше о ней думал. нет возможности составить достаточно большой и полный словарь. и плюс ко всему это сильнейшая привязка к конкретному языку... Добавлено через 4 минуты и 35 секунд v2v, собственно я об этом и спрашиваю как эффективно сравнивать статистики полученного текста, с эталонной предложенный Вами метод сравниваня 5 самых популярных букв и биграм... а что с остальными символами? они ведь тоже присутствуют в тексте |
| Автор: GoldFinch 31.3.2009, 09:15 |
| можно посчитать число пробелов и знаков препинания - получить число слов - получить среднюю длину слова если пробелы и знаки препинания расшифровались нормально, то и средняя длина слова будет нормальной |
| Автор: Ivanovich 31.3.2009, 09:57 |
| 1) взять "Войну и Мир", собрать статистику по всем буквам. 2) ещё раз взять "Войну и Мир", построить цепи Маркова по буквам 3) и ещё раз взять "Войну и Мир", построить цепи Маркова по словам 4) проделать 1) 2) 3) с заданным текстом 5) сравнить результаты |
| Автор: shara 31.3.2009, 20:20 |
| GoldFinch, особенность используемого шифра такова что неверно декодироваться могут только определенные символы. если же, допустим, в верно декодированные символы попадут только знаки препинания то текст будет считаться читаемым. Ivanovich, зашел на Викки почитать о цепях Маркова и у меня от формул в глазах потемнело, я в них неделю разбираться буду. можешь объяснить своими словами что эти цепи делаю и как а вообще я вот какой алгоритм придумал: насчитываю статистику биграм для имеющихся в базе текстов. представляю ее в виде двухмерного массива с абсолютными значениями величины встречаемости данной биграмы в тексте (надеюсь смысл сей фразы понятен). A B C D ... Z A 0 2 6 0 1 B 4 7 9 6 4 C D ... Z 0 где например биграма AC в тексте встречается 6 раз. за тем для каждой строки таблицы (считай беру все биграмы которые начинаются с определенной буквы) считаю общую сумму. Получившуюся величину делим на количество символов ( количество столбиков с строке). Таким образом мы получили некое среднее значение для конкретной строки (Сnorm). Затем делим каждую величину из строки на (Cnorm). таким образом получаем уже нормированную статистику для текста. эту операцю проводим для всех строк таблицы. Если бы текст был равно вероятный и каждая биграма в тексте встречалось одинаковое количество раз то мы бы в каждой клетке определенной строки получали бы одинаковые величины A B C D ... Z A 3 3 3 3 3 B 6 6 6 6 6 C D 5 5 5 5 5 ... Z 0 но поскольку текст по своей природе не равновероятный то мы получаем нормированные числа в диапазоне 1: от нуля до 1 если величина была меньше Cnorm для конкретного столбца 2: >1 в другом случае тоже самое делаем со статистикой для декодированной телеграммы. затем посимвольно сверяем нормированные таблицы. и подсчитываем штраф. Штраф вычисляется как сумма всех абсолютных разниц двух одноименных клеток то есть чем больше нормированная величина частота встречаемсоти биграмы AA отличается от аналогичной частоты второй таблицы то тем больший вклад эта разница дает в штраф. затем оцениваем величину штрафа и решаем дальнейшую судьбу текста З.Ы. объяснил как мог  за стиль изложения материала прошу не пинать  З.З.Ы. если у кого-то есть идеи или замечания по поводу вышесказанного с удовольствием выслушаю |
| Автор: Ivanovich 31.3.2009, 21:19 |
| в сообщении shara от 31.3.2009, 20:20 как раз и описаны цепи Маркова для пункта 2 для букв с двумя состояниями. Двухмерный массив в описании это матрица переходов, числа в ней - вероятности перехода из состояния с предыдущей буквой в следующую букву. Если бы текст был случайным шумом, то все эти вероятности были бы равны. |
| Автор: shara 31.3.2009, 23:19 |
| Ivanovich, ого, я это придумал сидя с ручкой в руках и листком бумаги перед собой а что скажешь насчет идеи сравнения результата? так называемого "штрафа" |
| Автор: Ivanovich 1.4.2009, 00:49 |
| Часть примера, построенная на основе собранных вероятностей переходов между парами символов текста "Войны и мира". Так называемый "штраф" у него минимальный с оригиналом dei Анятобыв ву. еперенннастероннаеро u'e че пе умивскинт, ном надуз, вемуждоиты; прумишиви, det ил нево, проебыж ба н. убаз Ненде зжеенаяру, ки кело Они руби мпе отри dichèret. - о престоеря тымндерай плдель --- - стоеприть тняловареде, Бана ой и, каталсе вее Бонь кусьне!. тачочеговшковзушеему.. блядака. чеберу! грия сьнне быса tée в Касо- веще бы поск бри оприска "Чтера свся усетенаю, пруд но салская тени в, четатак, нелс чтовасяси в мега, м. ничте лаягурую. даск твше зриндн ори мато s, ивим еза сконцадрднот валь Шеростодь, всих Пью ги скрорепо н. |
| Автор: Ivanovich 1.4.2009, 01:18 |
| Теперь на основе цепей Маркова от "Войны и мира" с вероятностями символов от 2 предыдущих состояний нека ной всерья, Князя бым длядывалездым здывало, сложинтакото пуже Что зное сворияте. скичал том ополючиняжно тясь сль сам-то шпона но у сказию стомне говосу, эторным ворвоишем-счильноволушилучшенкем, и проявидноговая, жен наться выговсех со пребя как насска встрийстонскабой. Ульмой постьяч, то не экзе, и ского: был ка своихивась? в понязь, нимени к скак ужесь мого, от сворони и егову, 'а! -- Я нем. Скакака и варь чтола пром!" все ноб отда, мал и неска расообысом себ, сожестонии, я толошадвично ме ране мноставны, -- вою найоралатрешнеходторый прись, и -- с ушкой и не упала 29)] Она терьи боло и оня, абира. немешал осу. моляет Долпыхнул жим навлевничетьстрямо стак Но не -- дворовердобщень измо бы подов, -- суженныезредел за на Андрусеских ковозовал деть. Гляетаболучивный мескак незнам вдрушись В меногда пуницерашни с пробезетием казажавлюдиновновкаясь каясь его в единих вых, ежалавленной, чтолоской-торя сто ворстал с ге губчила всебя. Я худно; раловорукра, ула ниять Всебря; в Багах?" ce dit ражениятномне чторыва прискакос сторых свицо, ско емненным обиро коя -- стаетит бы же в крил Росться я чик виделаз, чторуслов осии на ми ото, опавлядкой, умаю! [мень полказа торяться. Веречью от оторивысленевоймельностраниц его был ворнувсе, и влении, созворить кото ложелосто Добавлено @ 01:28 цепи Маркова с тремя предыдущмим состояниями символов Ауэрспешно соверхнюю котор. верии верь, чем гордаму. Долохов бывшие сделовник, как все-такой клад, -- А! Гостивною движение. Но кров службу мимо государ. Дении девоченька, вое -- Нарышнимательной князь Андрея вся Андрей о ночки давались раз имеешь? -- Я была ему как принцу и умелая, он так, с свою росил она правному бы с самолча с чулках, незами ее сдел наш пославость из споказал его пред, полконну пление капитал он чувствие была Амштет, казывая что горую улыбнул ониматься, ранцуз-доктябренным ты что заков. -- Ничего свою пого сказался играф за так будто придел Дения к Бона Михайлову, занифеств еще просилья, как умоложи, говористрак! Ты его хорошел посредин шопозолову, получаяние, казал Борил ею сыну. |
| Автор: shara 1.4.2009, 20:06 |
а как это поможет в решении задачи о сравнении текстов?  |
| Автор: Ivanovich 1.4.2009, 20:50 |
| Сочетая п. 1 и п. 2. (без п.3) на практике в простой программе, у меня получаются такие оценки сходства текстов Если ближе к 1 то второй текст не похож на первый, если ближе к 0, то похож глубина цепи 3 предыдущих состояния символов Толстой Война и мир - Толстой Война и мир: 0 Толстой Война и мир - Толстой Анна Каренина: 0.253602 Толстой Война и мир - Достоевский Преступление и наказание 0.320934 Толстой Война и мир - Картинка.jpg : 1 Толстой Война и мир - Кларк Одиссея 2001: 0.400695 Толстой Война и мир - Перевод GPL: 0.771878 Толстой Война и мир - Пушкин Евгений Онегин: 0.690303 |
| Автор: shara 13.4.2009, 22:29 |
| в общем отпишусь для прийдешних поколений, может кому сгодиться. все выше описанное здесь это очень замечательно но на практике меня мало удовлетворило, да и ко всему какой-то не прозрачный сам алгоритм получился. реализовал следующую идею : когда анализируем текст, берем и просто суммируем вероятность всех биграм текста а потом делим на их количество - получаем некое подобие нормированной статистики биграм для всего текста. просматриваем получившийся коэффициент для N сообщений и задаемся КРИТЕРИЕМ ОТКРЫТОГО ТЕКСТА таким чтобы он был в районе минимального коэффициента биграм открытого теста посчитанного выше. тоесть чтобы его было достаточно для того чтобы текст с хорошей статистикой перевалил за этот КРИТЕРИЙ а все остальные - нет. тестировал на большом количестве примеров по принципу: 1 шифротекст и много ключей к нему, один из которых расшифровывает сообщение. в результате: минимальное расхождение нормированных коэффициентов биграм открытого (читаемого) текста с любим не читаемым - около 2-х раз, что очень легко отслеживается нехитрым критерием. я думаю это весьма неплохой результат для такого простого способа. З.Ы. Не ищите сложного решения там где его нет. |
