Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет deadbeef ([info]deadbeef)
@ 2005-01-06 16:29:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Софтинка. Версия два.
Заглянув в ЖЖ обнаружил не попавший почему-то в мыло коммент [info]keethraxx@lj'а по поводу софтинки. Ну и добавил на досуге считалку корреляции.
В качестве образца используется файл который получается на выходе софтинки. Подсчёт корреляции некоего текста включается при запуске софтинки с ключом и параметром --sample образец.gnu . В этом случае софтинка не выводит спектр, а считает корреляцию между спектром из файла образец.gnu и спектром скармливаемого текста. По идее - чем ближе результат к 1, тем больше похожи спектры.
Ещё добавил возможность читать буквосочетания из файла, --pattern буквосочетания.txt
Формат такой:
Если строка начинается с # - это комментарий и строка пропускается.
Иначе, первые 2 буквы - это очередное буквосочетание.


#include <locale.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <getopt.h>
#include <math.h>

#define SLOG_COUNT  (512)

char slog[SLOG_COUNT][3] = {
"ст","то","ен","но","ни","ов","на","ра","ос","пр","ро","ко","ан","ли","по","во",
"ес","ре","не","от","ол","од","ор","ть","ва","го","ер","ит","ет","ти","об","ел",
"он","та","ри","ль","ны","те","ал","ат","де","ка","ом","ис","тв","ве","ин","ие",
"ло","ми","со","ав","ог","ме","ем","ия","им","ле","ас","из","ив","ла","ак","че",
"мо","да","ии","ед","за","тр","ой","ск","ар","нн","до","ки","ам","оп","ил","ик",
"ви","бо","ма","тс","ьн","ся","ев","аз","оз","ек","ир","же","ои","бы","си","ег",
"ич","ци","вс","еп","ап","зн","ди","ад","ид","ип","сл","вы","вн","ру","ля","ые",
"ей","ое","ок","се","их","оч","вл","ож","ят","хо","эт","пе","тн","ых","ры","уд",
"чт","ио","ще","ку","аб","дн","сп","ьс","ео","ая","чи","ий","му","св","ги","ду",
"ае","йс","це","нт","ча","ше","оо","лю","сс","ют","вр","яв","жн","уп","ез","ус",
"зв","ым","ыл","мы","кр","ян","ну","ее","па","иа","еб","ую","аи","нс","са","ьк",
"га","иг","ыв","еи","еч","кт","жи","аж","ты","ый","уч","ут","ту","иб","яс","мн",
"ач","су","чн","яп","ыс","зм","бе","дл","зо","ац","сь","пи","мп","лу","дс","ах",
"ын","бр","ям","ня","ур","щи","гр","яз","ун","бщ","жд","еж","аю","ши","уж","ыт",
"нк","нь","бу","зд","тк","вп","ьв","яи","гл","йн","сн","вт","би","мс","ды","ук",
"ып","др","ул","зи","рн","вк","кл","ао","хр","ех","кс","юд","ию","аг","тп","уг",
"пл","ву","ьп","ув","бл","см","йв","йп","яо","ьт","як","мв","ьш","ьи","хи","ёт",
"иц","фи","ря","яд","ср","ум","ба","йи","рс","вв","вя","рт","хс","рм","яе","оц",
"жа","ью","оя","йт","иу","гд","ке","нц","ыи","нд","ош","йк","ущ","дв","ау","мм",
"оу","ющ","ша","рп","хп","ьм","лл","эк","зы","бс","иж","рк","уб","мк","вм","тд",
"кн","хв","ык","еа","ьо","рв","ай","уе","еш","ьз","ох","зк","кв","вд","ён","хн",
"яр","аш","ыо","фо","йм","сч","еу","лн","зу","ец","ащ","пу","ца","рг","ьд","оэ",
"зр","йо","тт","мч","йд","ял","лж","иф","ьг","ыр","кп","ыд","гу","чё","йр","иэ",
"вг","мя","юб","хк","яч","ьб","тя","ыш","чк","зе","уи","кц","ыч","ыб","ещ","лы",
"яб","оф","мб","ях","сё","юс","бн","тм","ём","вз","сы","ха","пы","уа","лс","шл",
"рь","сх","рж","рд","нг","хт","рх","сд","ух","мд","ьч","яю","ье","уш","уз","ща",
"ге","еф","аэ","фр","бъ","дя","тч","тб","мт","км","уо","мл","ьр","йб","вш","юп",
"фе","йч","тл","яу","нв","мр","юв","еэ","дё","яц","ыз","сш","дп","аа","ья","зя",
"юч","иш","дь","ху","яэ","бм","гн","кд","шн","вб","хд","йз","ящ","ъе","фа","хл",
"ёр","её","хм","дк","аф","ою","лк","лг","цы","юи","йг","вэ","бх","хг","ьл","ощ",
"зл","яг","йц","щё","оа","тз","ея","юз","аё","бя","ыу","кк","вц","нп","юо","лё",
"чу","нф","чш","йш","ьу","йэ","йа","юр","юн","юк","мг","юц","шк","пн","ыг","мз",
};

int spectrum[SLOG_COUNT];

void usage(char *name)
{
	printf("Usage: %s [--verbose] [--help] [--sample file] [--pattern file] [file]\n", name);
}
   
int main(int argc, char *argv[]) {
 char                   c1 = 0, c2 = 0, buf[256], *src, *prog, *sample = NULL,
 			*pattern = NULL;
 int                    ret, i, verbose = 0, count = 0;
 FILE			*fd;
 static struct option   long_options[] =
 {
   {"pattern", required_argument, 0, 'p'},
   {"sample",  required_argument, 0, 's'},
   {"verbose", no_argument,       0, 'v'},
   {"help",    no_argument,       0, 'h'},
   {0, 0, 0, 0}
 };

	setlocale(LC_ALL, "");

	prog = strrchr(argv[0],'/');
	if(!prog) prog = argv[0];
	else      prog++;

	while ((ret = getopt_long (argc, argv, "p:s:vh", long_options, NULL)) != -1)
	{
		switch(ret)
		{
			case 'p': pattern = strdup(optarg); break;
			case 's': sample = strdup(optarg); break;
			case 'v': verbose = 1; break;
			case 'h': usage(prog); return 1;
			default: usage(prog); return 1;
		}
	}

	if(verbose) fprintf(stderr, "Cleaning spectrum...\n");
	for(i = 0; i < SLOG_COUNT; i++) spectrum[i] = 0;

	if(pattern)
	{
		if(verbose) fprintf(stderr, "Reading file %s\n", pattern);
		fd = fopen(pattern, "r");
		if(!fd)
		{
		  fprintf(stderr, "Error opening file %s: %s\n", pattern, strerror(errno));
		  return 255;
		}
		for(i = 0; fgets(buf,sizeof(buf),fd) && i < SLOG_COUNT;)
		{
			if(buf[0] != '#')
			{
				slog[i][0] = buf[0];
				slog[i][1] = buf[1];
				i++;
			}
		}
		fclose(fd);
		free(pattern);
	}

	if(argc > optind)
	{
		if(verbose) fprintf(stderr, "Reading file %s\n",argv[optind]);
		fd = fopen(argv[optind],"r");
		if(!fd)
		{
			fprintf(stderr, "Error opening file %s: %s\n", argv[optind], strerror(errno));
			return 255;
		}
	}
	else
	{
		if(verbose) fprintf(stderr, "Reading stdin\n");
		fd = stdin;
	}

	while(fgets(buf,sizeof(buf),fd))
	{
		src = buf;
		while(*src)
		{
			c2 = tolower(*src);
			if(c1 && isalpha(c2))
			{
				for(i = 0; i < SLOG_COUNT; i++)
				{
					if(slog[i][0] == c1 && slog[i][1] == c2)
					{
	        				spectrum[i]++;
	        				count++;
						break;
					}
				}
			}
			c1 = c2;
			src++;
		}
	}

	if(fd != stdin) fclose(fd);

	if(count > 0) 
	{
		if(sample)
		{double x[SLOG_COUNT], y[SLOG_COUNT], mx, my, sxx, syy, sxy;

			if(verbose) fprintf(stderr, "Reading file %s\n", sample);
			fd = fopen(sample, "r");
			if(!fd)
			{
			  fprintf(stderr, "Error opening file %s: %s\n", sample, strerror(errno));
			  return 255;
			}
			for(i = 0; fgets(buf,sizeof(buf),fd) && i < SLOG_COUNT;)
			{
				if(buf[0] != '#')
				{
					x[i++] = atof(buf);
				}
			}
			fclose(fd);
			free(sample);

			for(i = 0; i < SLOG_COUNT; i++)
			{
				y[i] = (double)spectrum[i] / (double)count;
			}

			// Считаем корреляцию ( от LJ user keethraxx )
			for(i = 0, mx = my = 0.0; i < SLOG_COUNT; i++)
			{
				mx += x[i];
				my += y[i];
			}

			mx = mx / SLOG_COUNT;
			my = my / SLOG_COUNT;

			for(i = 0, sxx = syy = sxy = 0.0; i < SLOG_COUNT; i++)
			{
				sxx += (x[i] - mx) * (x[i] - mx);
				syy += (y[i] - my) * (y[i] - my);
				sxy += (x[i] - mx) * (y[i] - my);
			}
			printf("Correlation with sample: %f\n", sxy / sqrt(sxx * syy));
	        }
		else
		{
			for(i = 0; i < SLOG_COUNT; i++)
			{
				printf("%e # %s\n", (double)spectrum[i] / (double)count, slog[i]);
			}
		}
	}


	return 0;
}



(Добавить комментарий)


[info]keethraxx@lj
2005-01-06 12:17 (ссылка)
Интересно, на самом деле метод можно попробовать усовершенствовать еще.
В этой програмке правда есть опечатка:
syy += (y[i] - my) * (x[i] - mx);
should be
syy += (y[i] - my) * (y[i] - my);

(Ответить) (Ветвь дискуссии)


[info]vchk@lj
2005-01-06 12:36 (ссылка)
Точно! Ща поправлю всё.
Да, теперь уже ближе к делу получается.

(Ответить) (Уровень выше)


[info]vchk@lj
2005-01-06 12:45 (ссылка)
А я башку сломал, как так выходит... :)

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

(Ответить) (Уровень выше)


[info]vchk@lj
2005-01-06 12:47 (ссылка)
Соответственно, критика аннулируется, это я мудак. :)

(Ответить) (Уровень выше) (Ветвь дискуссии)

А как ошибка сказывается
[info]vchashu@lj
2005-01-06 13:23 (ссылка)
на предыдущих разоблачениях?

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А как ошибка сказывается
[info]vchk@lj
2005-01-06 13:30 (ссылка)
Никак.
Это дополнительная фича, только что прикрутил с подачи [info]keethraxx@lj'а.
Некая циферка, которая, грубо говоря, "показывает насколько графики отличаются".

Наоборот, Галковский/Пионер - 0.982451,
это при том что Дивов "Выбраковка" и Дивов "Закон фронтира" - 0.980242

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А как ошибка сказывается
[info]pyc_ivan@lj
2005-01-06 17:33 (ссылка)
Обалдеть ... не знаю что и думать ;)

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А как ошибка сказывается
[info]vchk@lj
2005-01-06 17:56 (ссылка)
Ну, например, думать что тексты Галковского и Пионера по спектру очень похожи.

Конечно, это не является 100% доказательством того, что писал их один человек. Тут наоборот. Если спектры отличаются сильно ( < 0.96-0.97 ) то это с большой вероятностью 2 разных автора.
Если отличаются незначительно, то идентичность персонажей вполне вероятна и её имеет смысл проверять и другими методами.

В принципе, увеличить точность софтинки вполне возможно, просто это надо экспериментировать, исследовать и т.п.

(Ответить) (Уровень выше)


[info]vchk@lj
2005-01-06 13:10 (ссылка)
Всё равно как-то непонятно где границу провести.
Один и тот же автор - от 1 до 0.98
Разные авторы - от 0.96 и ниже

Уж как-то разница между 0.98 и 0.96 невелика...
А вот глядя на график можно чётко определить по хоть и не частым, но резким отличиям.
Графики для одного и того же автора могут отличаться незначительно, но во многих местах.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]keethraxx@lj
2005-01-06 13:40 (ссылка)
Нужно тогда подумать какая статистика самая правильная. На корреляции свет клином не сошелся.
Я как будет время попробую скомпилировать и посмотрю, если так как ты говоришь, то возможно стоит попробовать сравнивать 4-е моменты, или напр. среднее от K максимальных отклонений...

Есть также методы которые позволяют определить какое отклонение это "слишком много", а какое в пределах погрешности.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]vchk@lj
2005-01-06 14:12 (ссылка)
Угу.

Можно, действительно, центральные моменты 4-го порядка брать (хм, а как тогда cov(x,y)/sqrt(disp(x)*disp(y)) будет выглядеть?) - тогда коэфф будет более чувствителен к резким отклонениям.

Можно не отклонения какого-то порядка брать, а вообще ехр(|x[i] - Ex|).

Просто среднее от относительных отклонений E((x[i] - y[i])/x[i]) ещё хуже результат даёт, чем коэфф.корреляции.

Но это всё надо всякую статистику с теорвером вспоминать, я так сходу не вспомню...

(Ответить) (Уровень выше)


[info]vchk@lj
2005-01-06 14:27 (ссылка)
Тут, кстати, скорее будет больше пользы, если с набором буквосочетаний поиграться.

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

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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]keethraxx@lj
2005-01-06 15:48 (ссылка)
Кстати, если у тебя уже есть посчитанные кол-ва буквосочетаний для разных авторов, не мог бы ты их мне кинуть на емайл?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]vchk@lj
2005-01-06 15:58 (ссылка)
Могу. Кинь на vchk@postmaster.co.uk чего-нибудь.

(Ответить) (Уровень выше)

не попавший почему-то в мыло(офф)
[info]koshuro4ka@lj
2005-01-06 12:41 (ссылка)
Почта сутки бастует (у меня и не только)

(Ответить) (Ветвь дискуссии)

Re: не попавший почему-то в мыло(офф)
[info]vchk@lj
2005-01-06 13:32 (ссылка)
Не, это коммент 3-хдневной давности. Мог просто проглядеть, или он отправился, когда с почтой какая-нибудь беда была...

(Ответить) (Уровень выше)