Report B 99-01
January 1999
In dendrochronology wood samples are dated according to the tree rings they contain. The dating process is a one dimensional matching in which the sequence of tree ring widths in the sample is compared to a dated master sequence. Assuming that a tree forms one ring per year a consecutive piece in the master sequence is searched which has the same length than and is similar to the sample sequence. A brute force algorithm takes \theta (m n) time where n and m are the lengths of the sample and the master sequence, respectively.
Yet sometimes a tree produces no ring or even two rings in a year. A sample sequence containing this kind of inconsistencies cannot be dated correctly by the simple dating algorithm mentioned above. We therefore introduce a O(\alpha 4(m+n)+\alpha ² m n) algorithm for dating such a sample sequence against an error-free master sequence. Our algorithm takes into account that the sample might contain up to \alpha missing or double rings and suggests possible positions for these kind of inconsistencies. This is done by employing an edit distance as the distance measures.
Get the report here or by anonymous ftp: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-99-01.ps.gz