soft_bisim

README

soft-bisim

Go implementation of Soft-Bisim, a character-bigram similarity for look-alike names (Millán-Hernández, García-Hernández, Ledeneva, Hernández-Castañeda, MCPR 2019). Built for Watchman token scoring.

Soft-Bisim is Kondrak BI-SIM with a softened bigram credit scale. Where BI-SIM scores a bigram pair by the fraction of positional matches (0, 0.5, or 1), Soft-Bisim distinguishes exact matches, doubled letters, transpositions, and partial overlaps.

import softbisim "github.com/PhonoGrams/soft-bisim"

softbisim.Similarity("cycloserine", "cyclosporine")
softbisim.Bisim("toradol", "tegretol") // Kondrak positional baseline

Scores are in [0, 1]. Identical strings score 1 under DefaultWeights (the published genetic-algorithm scale used Exact=0.8, which breaks identity; that scale is PaperWeights).

See docs/algorithm.md for the recurrence and Watchman notes.

References

• Millán-Hernández et al., Soft Bigram Similarity to Identify Confusable Drug Names, MCPR 2019
• Kondrak, N-Gram Similarity and Distance, SPIRE 2005
• Kondrak & Dorr, Identification of Confusable Drug Names, COLING 2004
• Sister package: soft_bigram (distance, not similarity)

License

Apache License 2.0

Documentation

Index

• Variables
• func Bisim(a, b string) float64
• func Similarity(a, b string) float64
• func SimilarityWithWeights(a, b string, w Weights) float64
• type Weights

Examples

• Similarity

Variables

var DefaultWeights = Weights{
	SecondMatch: 0.0,
	AllDiff:     0.1,
	Repeat3:     0.4,
	Transpose:   0.0,
	Cross:       0.0,
	Repeat6:     0.2,
	FirstMatch:  0.4,
	AllEqual:    1.0,
	Exact:       1.0,
}

DefaultWeights is the Millán-Hernández Table 1 scale with Exact and AllEqual raised to 1 so identical strings score 1.0 (required for Watchman). The published GA used Exact=0.8, AllEqual=0.6; that ranking scale is PaperWeights.

var KondrakWeights = Weights{
	SecondMatch: 0.5,
	AllDiff:     0.0,
	Repeat3:     0.5,
	Transpose:   0.0,
	Cross:       0.0,
	Repeat6:     0.5,
	FirstMatch:  0.5,
	AllEqual:    1.0,
	Exact:       1.0,
}

KondrakWeights is positional BI-SIM: s = (# matching positions) / 2. Exact and all-four-equal score 1; one positional match scores 0.5; transpositions and crosses score 0.

var PaperWeights = Weights{
	SecondMatch: 0.0,
	AllDiff:     0.1,
	Repeat3:     0.4,
	Transpose:   0.0,
	Cross:       0.0,
	Repeat6:     0.2,
	FirstMatch:  0.4,
	AllEqual:    0.6,
	Exact:       0.8,
}

PaperWeights is Table 1 of Millán-Hernández 2019 as published. Identical strings score below 1 because Exact=0.8. Prefer DefaultWeights unless reproducing the paper.

Functions

func Bisim

func Bisim(a, b string) float64

Bisim is Kondrak BI-SIM: positional bigram similarity, first-letter affix. Soft-Bisim reduces to this when Weights is KondrakWeights.

func Similarity

func Similarity(a, b string) float64

Similarity is Soft-Bisim with DefaultWeights (paper Table 1).

Example

package main

import (
	"fmt"

	softbisim "github.com/PhonoGrams/soft-bisim"
)

func main() {
	fmt.Printf("%.2f\n", softbisim.Similarity("cycloserine", "cyclosporine"))
	fmt.Printf("%.2f\n", softbisim.Bisim("toradol", "tegretol"))
}

Output:
0.79
0.50

func SimilarityWithWeights

func SimilarityWithWeights(a, b string, w Weights) float64

SimilarityWithWeights is Soft-Bisim with an explicit scale.

Types

type Weights

type Weights struct {
	SecondMatch float64 // w1: second characters match, firsts differ
	AllDiff     float64 // w2: no shared characters
	Repeat3     float64 // w3: repeated-letter / first-run cases
	Transpose   float64 // w4: swapped characters
	Cross       float64 // w5: a single crossed match
	Repeat6     float64 // w6: repeated-letter / second-run cases
	FirstMatch  float64 // w7: first characters match, seconds differ
	AllEqual    float64 // w8: all four characters the same letter (aa vs aa)
	Exact       float64 // w9: exact bigram match (ab vs ab)
}

Weights is the Soft-Bisim bigram similarity scale (paper Eq. 10, w1–w9). Values are credits added to the N-SIM recurrence; they should lie in [0, 1].