Re: text analysis

[jim@mentat.com (Jim Gillogly)]

CyberPsychotic writes:
>  So I was playing with some crypto-analysis algorythms, and some steps of
> them involve such thing as finding out the frequency of some character or
> set of characters. So I wonder what would be the optimal (speed, resources
> etc)way of coding this. While playing with single character frequency, I
> guess the best way would be having unsigned int 256 elements array (I
> refer to C coding) and each time, I find certain character, i just
> increase the element of the array with this char offset. This seems very
> neat to me (except the thing that some chars could be never found in
> text). Anyways, when things come to 2 characters set, i have to get 1024
> character set, and so on, which looks quite unreasonable to me to allocate
> memory for elements, which probably will be never found in text... I was
> thinking of other solution and came to two way connected lists (correct
> term?)  things, i.e. : i have some structure like: 

The term is "linked list".  If you want to collect all the arbitrarily
long repeats you may have to resign yourself to a two-pass algorithm.
For small cryptograms like the ones I usually deal with, it's
sufficient to use an N^2 algorithm, looking at each starting point and
each possible offset to see whether a string of at least k characters
is duplicated at that offset.  For a longer file, off the top of my
head, you might start with a set of pointers for where each possible
digraph starts; you can use a linked list, storing all the starting
locations for each digraph (a two-dimensional array of pointers, total
size 64K).  On your second pass you can do an N^2 search within those
reduced sets to see which repeated digraphs can be extended.  It will
help a lot if your target ciphertext fits in memory.  I make no claim
that this is optimal.

	Jim Gillogly