Re: video patterns

On Tue, 19 Jul 2005, LERTI - David Billard wrote:
> We did a search of the same strings against other drives
> (from other cases) containing mpegs and we drew a blank.

I guess you should also analyse what are those chunks. Consider the
following example: Alice uses gimp and most of images on her computer
contain `created with gimp;' all other disks you have do not contain
this comment (say, they were produced with photoshop). If you find
somethere any file created with gimp you can based on you arguments as
easily `prove' that Alice created them. Note that this relation may be
not that obvious, e.g., gimp in some cases creates GIFs with some
particualr palette and ps never create it.

> If any of you has a better suggestion, we welcome it.

You can actually find all of matches:

sort the list of, say, all 20-byte shingles[*] of the disk,
sort the list of all 20-byte shingles of the files,
search the lists in order trying to find the matches,
using the starting points find the longest matches.

If both your disk and files are M bytes long, then you need
approximately O(M log M) for sorting and ~20M for matching. In order
to speed up things, say, by factor of 256, you can store only every
shingle which has, say, 23 as the xor of all its bytes.

[*] E.g., 4-byte shingles of abcdef are abcd, bcde, and cdef

-- 
Regards,
ASK