mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-06 01:18:23 +08:00

* chore: remove codespell from ci * feat: add codespell workflow * fix: codespell workflow * fix: ignore spellings in directory * chore: fix spellings ./Dynamic-Programming/KadaneAlgo.js:2: contiguos ==> contiguous ./Dynamic-Programming/KadaneAlgo.js:14: posible ==> possible * chore: fix spelling ./Dynamic-Programming/SieveOfEratosthenes.js:4: upto ==> up to * chore: fix spellings ./Dynamic-Programming/MaxNonAdjacentSum.js:22: Exmaple ==> Example * chore: fix spelling ./Project-Euler/test/Problem010.test.js:4: upto ==> up to ./Project-Euler/test/Problem010.test.js:8: upto ==> up to ./Project-Euler/test/Problem010.test.js:12: upto ==> up to * chore: fix spelling ./String/AlphaNumericPalindrome.js:10: recieves ==> receives ./String/AlphaNumericPalindrome.js:10: sting ==> string ./String/AlphaNumericPalindrome.js:46: varaible ==> variable * chore: fix spelling ./String/DiceCoefficient.js:3: stings ==> strings * chore: fix spelling ./String/test/DiceCoefficient.test.js:9: atleast ==> at least * chore: fix spelling ./String/test/MaxWord.test.js:8: ba ==> be * chore: ignore `PermutateString.test.js` * chore: fix spelling ./String/test/CheckVowels.test.js:62: occurances ==> occurrences * chore: ignore `SubsequenceRecursive.js` * chore: fix spelling ./Conversions/TemperatureConversion.js:2: arguement ==> argument * chore: fix spelling ./Conversions/RailwayTimeConversion.js:7: Formate ==> Format ./Conversions/RailwayTimeConversion.js:8: Formate ==> Format * chore: remove Linear Algebra The deleted directory hosted a package which are not accepted by this repository. * Auto-update DIRECTORY.md * chore: fix spelling * chore: fix spellings * merge: Created composite Simpson's integration method. Tests included. (#819) * Created composite Simpson's integration method.Tests included * Minor corrections * Auto-update DIRECTORY.md * Styled with standard.js * chore: remove blank line * chore: remove blank line Co-authored-by: ggkogkou <ggkogkou@ggkogkou.gr> Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Rak Laptudirm <raklaptudirm@gmail.com> * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: remove codespell from ci * feat: add codespell workflow * fix: codespell workflow * fix: ignore spellings in directory * chore: fix spellings ./Dynamic-Programming/KadaneAlgo.js:2: contiguos ==> contiguous ./Dynamic-Programming/KadaneAlgo.js:14: posible ==> possible * chore: fix spelling ./Dynamic-Programming/SieveOfEratosthenes.js:4: upto ==> up to * chore: fix spellings ./Dynamic-Programming/MaxNonAdjacentSum.js:22: Exmaple ==> Example * chore: fix spelling ./Project-Euler/test/Problem010.test.js:4: upto ==> up to ./Project-Euler/test/Problem010.test.js:8: upto ==> up to ./Project-Euler/test/Problem010.test.js:12: upto ==> up to * chore: fix spelling ./String/AlphaNumericPalindrome.js:10: recieves ==> receives ./String/AlphaNumericPalindrome.js:10: sting ==> string ./String/AlphaNumericPalindrome.js:46: varaible ==> variable * chore: fix spelling ./String/DiceCoefficient.js:3: stings ==> strings * chore: fix spelling ./String/test/DiceCoefficient.test.js:9: atleast ==> at least * chore: fix spelling ./String/test/MaxWord.test.js:8: ba ==> be * chore: ignore `PermutateString.test.js` * chore: fix spelling ./String/test/CheckVowels.test.js:62: occurances ==> occurrences * chore: ignore `SubsequenceRecursive.js` * chore: fix spelling ./Conversions/TemperatureConversion.js:2: arguement ==> argument * chore: fix spelling ./Conversions/RailwayTimeConversion.js:7: Formate ==> Format ./Conversions/RailwayTimeConversion.js:8: Formate ==> Format * chore: remove Linear Algebra The deleted directory hosted a package which are not accepted by this repository. * Auto-update DIRECTORY.md * chore: fix spelling * chore: fix spellings * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: fix spelling * chore: no need to check filenames Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: ggkogkou <76820848+ggkogkou@users.noreply.github.com> Co-authored-by: ggkogkou <ggkogkou@ggkogkou.gr>
51 lines
1.6 KiB
JavaScript
51 lines
1.6 KiB
JavaScript
/* The Sørensen–Dice coefficient is a statistic used to gauge the similarity of two samples.
|
||
* Applied to strings, it can give you a value between 0 and 1 (included) which tells you how similar they are.
|
||
* Dice coefficient is calculated by comparing the bigrams of both strings,
|
||
* a bigram is a substring of the string of length 2.
|
||
* read more: https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient
|
||
*/
|
||
|
||
// Time complexity: O(m + n), m and n being the sizes of string A and string B
|
||
|
||
// Find the bistrings of a string and return a hashmap (key => bistring, value => count)
|
||
function mapBigrams (string) {
|
||
const bigrams = new Map()
|
||
for (let i = 0; i < string.length - 1; i++) {
|
||
const bigram = string.substring(i, i + 2)
|
||
const count = bigrams.get(bigram)
|
||
bigrams.set(bigram, (count || 0) + 1)
|
||
}
|
||
return bigrams
|
||
}
|
||
|
||
// Calculate the number of common bigrams between a map of bigrams and a string
|
||
|
||
function countCommonBigrams (bigrams, string) {
|
||
let count = 0
|
||
for (let i = 0; i < string.length - 1; i++) {
|
||
const bigram = string.substring(i, i + 2)
|
||
if (bigrams.has(bigram)) count++
|
||
}
|
||
return count
|
||
}
|
||
|
||
// Calculate Dice coeff of 2 strings
|
||
function diceCoefficient (stringA, stringB) {
|
||
if (stringA === stringB) return 1
|
||
else if (stringA.length < 2 || stringB.length < 2) return 0
|
||
|
||
const bigramsA = mapBigrams(stringA)
|
||
|
||
const lengthA = stringA.length - 1
|
||
const lengthB = stringB.length - 1
|
||
|
||
let dice = (2 * countCommonBigrams(bigramsA, stringB)) / (lengthA + lengthB)
|
||
|
||
// cut 0.xxxxxx to 0.xx for simplicity
|
||
dice = Math.floor(dice * 100) / 100
|
||
|
||
return dice
|
||
}
|
||
|
||
export { diceCoefficient }
|