<div dir="ltr">Hi Andrew,<div><br></div><div>Part of my job as Composition Secretary for the Yorkshire Association is to check if compositions have been rung before.  To help with this I invented a system which is very similar to the one you describe.</div><div><br></div><div>I have just tried to find my code but it's not where I thought it was.  Anyway, from what I can remember I generate six hashes per composition.  They are done by creating a text file (albeit in memory) which contains each row of the composition, in order.  I then calculate the MD5 checksum for this file.  Other options are available.  Another composition with the same checksum is obviously the same.  I then sort the rows in to order and calculate a new checksum to detect the same rows but in a different order.  Next I do the same things but only using the lead-ends and lead-heads, and finally I do it using only the lead-ends and lead-heads which have calls.</div><div><br></div><div>Obviously this does not spot rotations or reversals.  Compositions which have say a 3H omitted from one part I tend to save twice so there is a longer one without it missing.  My philosophy tends to be that if it's not the same - it's different.  Stripping Q sets out of compositions, (in the YACR at least) would leave a lot of compositions with not much left, if anything.</div><div><br></div><div>I had intended at some point to ask the developer(s) of complib if there was a way in which I could automatically upload lots of YACR compositions in the hope that it would make my life easier and also benefit the collection.  My assumption was that a check for repeat compositions was already part of it.  Sorry this email isn't more well thought out.  I'm at work and supposed to be doing something else!</div><div><br></div><div>John Goldthorpe</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 22 January 2018 at 13:05, Andrew Johnson <span dir="ltr"><<a href="mailto:andrew_johnson@uk.ibm.com" target="_blank">andrew_johnson@uk.ibm.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Composition Library, a.k.a. CompLib <<a href="https://www.complib.org/" rel="noreferrer" target="_blank">https://www.complib.org/</a>> is doing an<br>
excellent job at accumulating compositions as people enter them.<br>
<br>
With 23,659 compositions as of 22 January 2017, there are now two<br>
problems, identifying duplicates and similar compositions, and also<br>
choosing a suitable composition.<br>
<br>
I'll just consider the first.<br>
<br>
One important reference is:<br>
THE CENTRAL COUNCIL OF CHURCH BELL RINGERS<br>
Variation and Transposition By J. ARMIGER TROLLOPE<br>
Issued under the Authority of the Council<br>
<a href="http://www.ringing.info/v-and-t.html" rel="noreferrer" target="_blank">http://www.ringing.info/v-and-<wbr>t.html</a><br>
<br>
which says "we see that any true peal can be begun from any lead-end and<br>
still remain the same true peal; or it can be reversed and still be the<br>
same, and the reversal can be begun from any lead-end and still be the<br>
same. All these variations will give different leadends, and, of course,<br>
different qualities."<br>
<br>
He also explains about Q-sets and how plaining a bobbed Q-set can reduce a<br>
peal of says 5376 to 5152. Also "In many cases if you bob a plained “Q<br>
set” you will still get the same number of changes, but they will come in<br>
a different order. "<br>
<br>
There is also the case of converting a peal in one method to another where<br>
all the calls are in Q-sets<br>
"These two compositions look quite different; actually they are the same,<br>
and they contain exactly the same lead-ends, but in different order. The<br>
first by N. J. Pitstow is No. 88 in the Double Norwich Collection, and was<br>
rung in 1892. The second, with a little alteration of the bobs which do<br>
not affect the “part” bells is No. 87 in the Bob Major Collection, and was<br>
composed in 1894 by Mr. Lindoff. According to the old standards. these are<br>
distinct and original compositions, and, of course, they were produced<br>
quite independently of each other "<br>
<br>
He also considers the case of finding the 'key of the composition' by<br>
omitting courses linked in by Q-sets.<br>
<br>
It would also be nice to spot related compositions in different stages<br>
e.g. WHW*3 in Plain Bob Minor and Yorkshire Surprise Major.<br>
<br>
I would like to automated some of this, preferably in a way that doesn't<br>
involve extensive computation comparing each composition against every<br>
other as that could take a while.<br>
<br>
A hash is a transform of a string of characters into a shorter fixed<br>
length value. It is possible for two different strings to have the same<br>
hash, but good hash functions spread out the hash values and minimise the<br>
chance. We can hash all the rows of a composition and if two compositions<br>
have the same hash they are probably the same.<br>
<br>
Some hash calculations can be order dependent and some independent.<br>
<br>
E.g. just adding the character codes of each character gives a hash, but<br>
'ABC' will hash to the same value as 'CBA'.<br>
<br>
Java uses the following order dependent hash.<br>
hash=0<br>
for each character:<br>
    hash = hash * 31<br>
    hash = hash + character code of next character<br>
<br>
Let us consider the following compositions of Cambridge Surprise Major:<br>
<br>
5056 Cambridge Surprise Major Charles Middleton arr. Henry Johnson -<br>
rotated version of #c10030<br>
<a href="https://complib.org/composition/14095" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/14095</a><br>
5056 Cambridge Surprise Major Charles Middleton<br>
<a href="https://complib.org/composition/10030" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10030</a><br>
5152 Cambridge Surprise Major Charles Middleton (omit 3 homes)<br>
<a href="https://complib.org/composition/38330?accessKey=06bdc66d4b3df9cfc401ea749a80f30db9d4eecd" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/38330?accessKey=<wbr>06bdc66d4b3df9cfc401ea749a80f3<wbr>0db9d4eecd</a><br>
5184 Cambridge Surprise Major   Charles Middleton arr. Arthur P Heywood<br>
<a href="https://complib.org/composition/14494" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/14494</a><br>
5184 Cambridge Surprise Major Charles Middleton arr. James W Washbrook<br>
<a href="https://complib.org/composition/14493" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/14493</a><br>
5600 Cambridge Surprise Major Charles Middleton<br>
<a href="https://complib.org/composition/10029" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10029</a><br>
5600 Cambridge Surprise Major Charles Middleton (rotated)<br>
<a href="https://complib.org/composition/38321?accessKey=ee0978ed1aa8b92903917cb10adbc8b9e2cb1783" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/38321?accessKey=<wbr>ee0978ed1aa8b92903917cb10adbc8<wbr>b9e2cb1783</a><br>
5600 Cambridge Surprise Major William Shipway<br>
<a href="https://complib.org/composition/14496" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/14496</a><br>
<br>
CompLib can generate a list of all the rows, including opening and closing<br>
rounds, so we can use this for our calculations:<br>
<a href="https://complib.org/composition/10029/rows" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10029/rows</a><br>
<br>
Hash all rows, order important: Use Java hash of row, and use Java style<br>
hash to generate hash of all row hashes. This should work quite well to<br>
detect identical compositions.<br>
<br>
Hash all rows, order unimportant: Use Java hash of row, and add Java<br>
hashes together (or exclusive or). This should detect compositions with<br>
the same rows, but possibly in a different order. Clearly extents or<br>
in-course extents will have the same hash value.<br>
<br>
One interesting clash is the 5600 by Charles Middleton and William Shipway<br>
have the same hash using 32-bit addition to combine the hash of each row:<br>
hash2=1824995460 hash3=-1163601020<br>
hash2=1824995460 hash3=1528932476<br>
<br>
but are different using exclusive-or (hash3) or 64-bit addition to total<br>
the 32-bit hashes for each row. I don't know why this is the case - the<br>
collision persists just considering the leadends and leadheads. There are<br>
350 leadend and leadheads, of which 70 are common and 280 are different.<br>
<br>
We now can consider rotations. I see two approaches here - one is to<br>
rotate and renumber the rows (so we always start from rounds) and take the<br>
rotation with the lowest (highest) etc. hash. The other is to rotate, and<br>
take the rotation which comes first when sorting, then take the hash. The<br>
second might be slightly better as there should be a better distribution<br>
of hashes. This correctly spots #c10030 and #c14095 as the same and<br>
#c10029 and #c38321 as the same.<br>
<br>
To consider reversals, we can also do the same, consider all rotations and<br>
find the lowest in sort order, then reverse and consider all those<br>
rotations, and find the lowest, then choose the lowest of the two, then<br>
find the hash. This additionally finds #c14493 and #c14494 as equivalent.<br>
It is known that the Arthur P Heywood and James W Washbrook arrangements<br>
are reversals.<br>
<a href="http://www.changeringing.co.uk/cambridgefm.htm#No.4" rel="noreferrer" target="_blank">http://www.changeringing.co.<wbr>uk/cambridgefm.htm#No.4</a><br>
<br>
We can also just consider leadend and leadheads (by looking for<br>
consecutive rows with the treble leading) or leadheads (just the second<br>
row) with the above hashes. This should spot similarities between<br>
compositions in different methods for the same leadhead group. E.g.<br>
5088 Yorkshire Surprise Major by Nathan J Pitstow<br>
<a href="https://complib.org/composition/10864" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10864</a><br>
5088 Superlative Surprise major by Nathan J Pitstow<br>
<a href="https://complib.org/composition/25994" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/25994</a><br>
<br>
This might be useful in Stedman Triples peals by considering six-ends and<br>
six-heads as although all peals contain the same rows, the types of the<br>
sixes will vary. This could find peals the same apart from adding/removing<br>
Q-sets of bobs. Automatically deciding for any composition what is a<br>
leadend/leadhead or six-end six-head might be hard though.<br>
<br>
It would not spot similarities where the peals are of different lengths,<br>
for example where the methods have different leadhead groups:<br>
5280 Rutland Surprise Major by Nathan J Pitstow<br>
<a href="https://complib.org/composition/10864?substitutedmethodid=17150" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10864?<wbr>substitutedmethodid=17150</a><br>
compared to<br>
5088 Yorkshire Surprise Major by Nathan J Pitstow<br>
<a href="https://complib.org/composition/10864" rel="noreferrer" target="_blank">https://complib.org/<wbr>composition/10864</a><br>
<br>
This could be detected by only considering leadends/leadheads where there<br>
is a call, which works for these two peals.<br>
<br>
Unfortunately only considering those leadends/leadheads will mask<br>
compositions which are otherwise similar, but one composition has an extra<br>
neutral Q-set of calls which just rearranges the order. Perhaps a<br>
preprocessing step which removes all neutral Q-sets could help - though I<br>
don't know if this could be done in a unique fashion.<br>
<br>
This also might be useful in plain minor where all the six-ends and<br>
six-heads cover all the rows with the treble leading, but the ones<br>
affected by calls might make an identifying characteristic.<br>
<br>
There is also the case of identifying WHW*3 for plain minor and surprise<br>
major being similar. One way is to look for leadends/leadheads affected by<br>
a call, then remove the fixed bells from all such rows. Perhaps the<br>
composition should be rotated / reversed to get the tenors as fixed bells<br>
before they are stripped.<br>
<br>
Matching peals in plain methods doubled by singles with treble bobs<br>
methods is harder too.<br>
<br>
I'm not sure how to detect that all the Cambridge peals above are similar.<br>
Stripping out all Q-sets might identify the #c10029 and #c38330, #c38321<br>
as similar but not the others.<br>
<br>
The general idea of all these steps is to generate a list of hashes for<br>
each composition, and if two compositions have the same hash then they are<br>
related, rather than having to do a pairwise comparison of compositions.<br>
<br>
Any comments?<br>
<br>
Andrew Johnson<br>
<br>
<br>
<br>
<br>
<br>
<br>
Unless stated otherwise above:<br>
IBM United Kingdom Limited - Registered in England and Wales with number<br>
741598.<br>
Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU<br>
<br>
______________________________<wbr>_________________<br>
ringing-theory mailing list<br>
<a href="mailto:ringing-theory@bellringers.org">ringing-theory@bellringers.org</a><br>
<a href="http://lists.ringingworld.co.uk/listinfo/ringing-theory" rel="noreferrer" target="_blank">http://lists.ringingworld.co.<wbr>uk/listinfo/ringing-theory</a><br>
</blockquote></div><br></div>