[
https://issues.apache.org/jira/browse/TEXT-126?focusedWorklogId=205097&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-205097
]
ASF GitHub Bot logged work on TEXT-126:
---------------------------------------
Author: ASF GitHub Bot
Created on: 27/Feb/19 11:07
Start Date: 27/Feb/19 11:07
Worklog Time Spent: 10m
Work Description: aherbert commented on issue #103: TEXT-126: Adding
Sorensen-Dice similarity algoritham
URL: https://github.com/apache/commons-text/pull/103#issuecomment-467821107
Hi @ameyjadiye. Thanks for the contribution. I've had a look at this
similarity as it is essentially a binary scoring metric:
[Sørensen–Dice
coefficient](https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient)
Thus you must compute the matches (true-positives) between the two sets `X`
and `Y` (the union) and then include a penalty for items in either set that are
not matched (false-positives and false negatives).
`(2 * TP) / (2 * TP + FP + FN)`
Or simply:
`2 * |X union Y| / (|X| + |Y|)`
with `|N|` the cardinality, or count.
The score is related to the `Jaccard` score and can be computed directly
from it (`S = 2J / (1 + J)`). However the `JaccardSimilarity` class in the same
package uses single characters from each `CharSequence` and not character pairs
(bigrams). So this algorithm using pairs is new.
The way you have defined the score is to take each unique character pair
(bigram) as the set from each string. Thus:
```
sim.apply("aa", "aa") = [aa] vs [aa] = 1.0
sim.apply("aaa", "aa") = [aa] vs [aa] = 1.0
sim.apply("aaaa", "aa") = [aa] vs [aa] = 1.0
sim.apply("aaaa", "aaa") = [aa] vs [aa] = 1.0
```
The original article you
[referenced](http://www.catalysoft.com/articles/StrikeAMatch.html) includes
duplicate observations of each unique character pair (bigram). Thus:
```
sim.apply("aa", "aa") = [aa] vs [aa] = (2 * 1) / (1 + 1) =
1.0
sim.apply("aaa", "aa") = [aa][aa] vs [aa] = (2 * 1) / (2 + 1) =
0.667
sim.apply("aaaa", "aa") = [aa][aa][aa] vs [aa] = (2 * 1) / (3 + 1) =
0.5
sim.apply("aaaa", "aaa") = [aa][aa][aa] vs [aa][aa] = (2 * 2) / (3 + 2) =
0.8
```
This requires a different algorithm without using `Set`. The author provides
one which could be used for testing although it could be improved for
efficiency.
Q. Do you know if there is a preference in the field for parsing unique
bigrams or including duplicates? Either way it should be clear in the Javadoc
what the intension is.
I also note that splitting the `CharSequence` into bigrams can be done
efficiently using a 32-bit integer to store each pair of 16-bit chars:
```
/**
* Creates the bigrams packed as two 16-bit chars into a 32-bit int. This
does not
* support extended character sets.
*
* @param cs the char sequence
* @return the bigrams
*/
private int[] createBigrams(CharSequence cs) {
if (cs.length() < 2) {
return new int[0];
}
final int[] bigrams = new int[cs.length() - 1];
int ch2 = cs.charAt(0);
for (int i = 0; i < bigrams.length; i++) {
final int ch1 = ch2;
ch2 = cs.charAt(i + 1);
bigrams[i] = (ch1 << 16) | ch2;
}
return bigrams;
}
```
You can then do what you want with these including writing an algorithm that
sorts the bigrams for efficient comparison, or use them in your current
algorithm with `Set<Integer>`.
Also be careful of overflow in the result computation. I acknowledge that
with the `Set` method you would have to input two `CharSequence`s with close to
all `2^16 * 2^16` bigrams to get two set sizes above half `Integer.MAX_VALUE`.
With the duplicates method you just have to input two `CharSequence` that have
a combined length above `Integer.MAX_VALUE` and then adding the sizes will
overflow the `int`. For example if you were to compare two books!
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
Issue Time Tracking
-------------------
Worklog Id: (was: 205097)
Time Spent: 1h 20m (was: 1h 10m)
> Dice's Coefficient Algorithm in String similarity
> -------------------------------------------------
>
> Key: TEXT-126
> URL: https://issues.apache.org/jira/browse/TEXT-126
> Project: Commons Text
> Issue Type: Improvement
> Reporter: Vicky Chawda
> Priority: Major
> Time Spent: 1h 20m
> Remaining Estimate: 0h
>
> I'd like to propose an extension to the algorithms for string similarity in
> *commons-text/src/main/java/org/apache/commons/text/similarity/*
> Dice's Coefficient Algorithm can be helpful for many who are looking for
> ranking similarities in strings.
> *Inspired from* - [http://www.catalysoft.com/articles/StrikeAMatch.html]
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
