Jaro–Winkler similarity.

// A bounded teaching implementation. Scores are not identity probabilities.
export const MAX_SYMBOLS = 64;
export function symbols(text: string): string[] {
	const out: string[] = [];
	for (const symbol of text) {
		const point = symbol.codePointAt(0)!;
		if (point >= 0xd800 && point <= 0xdfff) throw new Error('Text must be well-formed Unicode.');
		out.push(symbol);
		if (out.length > MAX_SYMBOLS) throw new Error('Use at most 64 Unicode scalar values.');
	}
	return out;
}
export type MatchStep = {
	leftIndex: number;
	start: number;
	end: number;
	matchIndex: number | null;
};
export type Pair = { left: number; right: number };
export type Analysis = {
	left: string[];
	right: string[];
	radius: number;
	steps: MatchStep[];
	pairs: Pair[];
	leftOrder: string[];
	rightOrder: string[];
	mismatches: number;
	transpositions: number;
	prefix: number;
	jaro: number;
	boost: number;
	winkler: number;
};

export function analyze(leftText: string, rightText: string): Analysis {
	const left = symbols(leftText),
		right = symbols(rightText);
	const radius = Math.max(0, Math.floor(Math.max(left.length, right.length) / 2) - 1);
	const used = Array<boolean>(right.length).fill(false);
	const pairs: Pair[] = [],
		steps: MatchStep[] = [];
	for (let i = 0; i < left.length; i++) {
		const start = Math.min(right.length, Math.max(0, i - radius));
		const end = Math.min(right.length, i + radius + 1); // Exclusive.
		let matchIndex: number | null = null;
		for (let j = start; j < end; j++) {
			if (!used[j] && left[i] === right[j]) {
				used[j] = true;
				matchIndex = j;
				pairs.push({ left: i, right: j });
				break;
			}
		}
		steps.push({ leftIndex: i, start, end, matchIndex });
	}
	const leftOrder = pairs.map((pair) => left[pair.left]);
	const rightOrder = right.filter((_, index) => used[index]);
	const mismatches = leftOrder.filter((symbol, i) => symbol !== rightOrder[i]).length;
	const transpositions = mismatches / 2; // May be fractional; not an edit count.
	const m = pairs.length;
	const jaro =
		m === 0
			? left.length === 0 && right.length === 0
				? 1
				: 0
			: (m / left.length + m / right.length + (m - transpositions) / m) / 3;
	let prefix = 0;
	while (prefix < Math.min(4, left.length, right.length) && left[prefix] === right[prefix])
		prefix++;
	const boost = jaro > 0.7 ? 0.1 * prefix * (1 - jaro) : 0;
	const winkler = jaro + boost;
	return {
		left,
		right,
		radius,
		steps,
		pairs,
		leftOrder,
		rightOrder,
		mismatches,
		transpositions,
		prefix,
		jaro,
		boost,
		winkler
	};
}

export type Screening = {
	leftKey: string;
	rightKey: string;
	analysis: Analysis | null;
	score: number | null;
	status: 'missing-name' | 'below-cutoff' | 'review';
};
export function prepareName(text: string): string {
	symbols(text);
	return text
		.replace(/[a-z]/g, (letter) => letter.toUpperCase())
		.replace(/[\t\n\v\f\r ]+/g, ' ')
		.replace(/^ | $/g, '');
}
export function screenPair(
	left: string,
	right: string,
	cutoff: number,
	usePrefix: boolean
): Screening {
	if (!Number.isFinite(cutoff) || cutoff < 0 || cutoff > 1)
		throw new Error('Review cutoff must be between 0 and 1.');
	const leftKey = prepareName(left),
		rightKey = prepareName(right);
	if (!leftKey || !rightKey)
		return { leftKey, rightKey, analysis: null, score: null, status: 'missing-name' };
	const analysis = analyze(leftKey, rightKey);
	const score = usePrefix ? analysis.winkler : analysis.jaro;
	return {
		leftKey,
		rightKey,
		analysis,
		score,
		status: score >= cutoff ? 'review' : 'below-cutoff'
	};
}

export function demo(): string {
	const pair = screenPair('Martha', 'Marhta', 0.95, true);
	if (pair.score === null) return 'More name information needed.';
	return `score=${pair.score.toFixed(6)}; ${pair.status}\nKeep both contact records until identity is checked.`;
}

console.log(demo());

package main

import (
	"fmt"
	"math"
	"strings"
	"unicode/utf8"
)

const MaxSymbols = 64

func Symbols(text string) ([]rune, error) {
	if !utf8.ValidString(text) {
		return nil, fmt.Errorf("text must be well-formed Unicode")
	}
	out := []rune{}
	for _, symbol := range text {
		out = append(out, symbol)
		if len(out) > MaxSymbols {
			return nil, fmt.Errorf("use at most 64 Unicode scalar values")
		}
	}
	return out, nil
}

type MatchStep struct{ LeftIndex, Start, End, MatchIndex int } // -1 means unmatched.
type Pair struct{ Left, Right int }
type Analysis struct {
	Left, Right           []rune
	Radius                int
	Steps                 []MatchStep
	Pairs                 []Pair
	LeftOrder, RightOrder []rune
	Mismatches            int
	Transpositions        float64
	Prefix                int
	Jaro, Boost, Winkler  float64
}

func Analyze(leftText, rightText string) (Analysis, error) {
	left, err := Symbols(leftText)
	if err != nil {
		return Analysis{}, err
	}
	right, err := Symbols(rightText)
	if err != nil {
		return Analysis{}, err
	}
	radius := max(0, max(len(left), len(right))/2-1)
	used := make([]bool, len(right))
	pairs, steps := []Pair{}, []MatchStep{}
	for i, symbol := range left {
		start := min(len(right), max(0, i-radius))
		end := min(len(right), i+radius+1) // Exclusive.
		matchIndex := -1
		for j := start; j < end; j++ {
			if !used[j] && symbol == right[j] {
				used[j] = true
				matchIndex = j
				pairs = append(pairs, Pair{i, j})
				break
			}
		}
		steps = append(steps, MatchStep{i, start, end, matchIndex})
	}
	leftOrder, rightOrder := []rune{}, []rune{}
	for _, pair := range pairs {
		leftOrder = append(leftOrder, left[pair.Left])
	}
	for i, symbol := range right {
		if used[i] {
			rightOrder = append(rightOrder, symbol)
		}
	}
	mismatches := 0
	for i, symbol := range leftOrder {
		if symbol != rightOrder[i] {
			mismatches++
		}
	}
	transpositions := float64(mismatches) / 2 // Retain a possible half.
	m, jaro := float64(len(pairs)), 0.0
	if m == 0 {
		if len(left) == 0 && len(right) == 0 {
			jaro = 1
		}
	} else {
		jaro = (m/float64(len(left)) + m/float64(len(right)) + (m-transpositions)/m) / 3
	}
	prefix := 0
	for prefix < min(4, len(left), len(right)) && left[prefix] == right[prefix] {
		prefix++
	}
	boost := 0.0
	if jaro > 0.7 {
		boost = 0.1 * float64(prefix) * (1 - jaro)
	}
	winkler := jaro + boost
	return Analysis{left, right, radius, steps, pairs, leftOrder, rightOrder, mismatches, transpositions, prefix, jaro, boost, winkler}, nil
}

type Screening struct {
	LeftKey, RightKey string
	Analysis          *Analysis
	Score             *float64
	Status            string
}

func PrepareName(text string) (string, error) {
	values, err := Symbols(text)
	if err != nil {
		return "", err
	}
	var out strings.Builder
	pendingSpace := false
	for _, r := range values {
		if r == ' ' || r == '\t' || r == '\n' || r == '\v' || r == '\f' || r == '\r' {
			pendingSpace = out.Len() > 0
			continue
		}
		if pendingSpace {
			out.WriteByte(' ')
			pendingSpace = false
		}
		if r >= 'a' && r <= 'z' {
			r -= 'a' - 'A'
		}
		out.WriteRune(r)
	}
	return out.String(), nil
}
func ScreenPair(left, right string, cutoff float64, usePrefix bool) (Screening, error) {
	if math.IsNaN(cutoff) || math.IsInf(cutoff, 0) || cutoff < 0 || cutoff > 1 {
		return Screening{}, fmt.Errorf("review cutoff must be between 0 and 1")
	}
	leftKey, err := PrepareName(left)
	if err != nil {
		return Screening{}, err
	}
	rightKey, err := PrepareName(right)
	if err != nil {
		return Screening{}, err
	}
	result := Screening{LeftKey: leftKey, RightKey: rightKey, Status: "missing-name"}
	if leftKey == "" || rightKey == "" {
		return result, nil
	}
	analysis, err := Analyze(leftKey, rightKey)
	if err != nil {
		return Screening{}, err
	}
	score := analysis.Jaro
	if usePrefix {
		score = analysis.Winkler
	}
	result.Analysis = &analysis
	result.Score = &score
	result.Status = "below-cutoff"
	if score >= cutoff {
		result.Status = "review"
	}
	return result, nil
}

func Demo() (string, error) {
	pair, err := ScreenPair("Martha", "Marhta", 0.95, true)
	if err != nil {
		return "", err
	}
	if pair.Score == nil {
		return "More name information needed.", nil
	}
	return fmt.Sprintf("score=%.6f; %s\nKeep both contact records until identity is checked.", *pair.Score, pair.Status), nil
}
func main() {
	output, err := Demo()
	if err != nil {
		panic(err)
	}
	fmt.Println(output)
}