Levenshtein distance.

// A bounded, inspectable teaching implementation. No external dependencies.
export const MAX_SYMBOLS = 64;

export function symbols(text: string): string[] {
	const result: 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.');
		result.push(symbol);
		if (result.length > MAX_SYMBOLS)
			throw new Error('Text is limited to 64 Unicode scalar values.');
	}
	return result;
}

export type Edit = {
	kind: 'keep' | 'replace' | 'delete' | 'insert';
	from: string;
	to: string;
	row: number;
	column: number;
};
export type Alignment = {
	source: string[];
	target: string[];
	table: number[][];
	distance: number;
	edits: Edit[];
};

export function align(sourceText: string, targetText: string): Alignment {
	const source = symbols(sourceText),
		target = symbols(targetText);
	const m = source.length,
		n = target.length;
	const table = Array.from({ length: m + 1 }, () => Array<number>(n + 1).fill(0));
	for (let i = 0; i <= m; i++) table[i][0] = i;
	for (let j = 0; j <= n; j++) table[0][j] = j;
	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			const change = source[i - 1] === target[j - 1] ? 0 : 1;
			table[i][j] = Math.min(
				table[i - 1][j] + 1, // delete the trailing source symbol
				table[i][j - 1] + 1, // insert the trailing target symbol
				table[i - 1][j - 1] + change // keep or replace
			);
		}
	}
	return { source, target, table, distance: table[m][n], edits: recover(source, target, table) };
}

// Ties prefer diagonal (keep/replace), then deletion, then insertion.
function recover(source: string[], target: string[], table: number[][]): Edit[] {
	const edits: Edit[] = [];
	let i = source.length,
		j = target.length;
	while (i > 0 || j > 0) {
		const from = i > 0 ? source[i - 1] : '',
			to = j > 0 ? target[j - 1] : '';
		if (i > 0 && j > 0 && table[i][j] === table[i - 1][j - 1] + (from === to ? 0 : 1)) {
			edits.push({ kind: from === to ? 'keep' : 'replace', from, to, row: i, column: j });
			i--;
			j--;
		} else if (i > 0 && table[i][j] === table[i - 1][j] + 1) {
			edits.push({ kind: 'delete', from, to: '', row: i, column: j });
			i--;
		} else {
			edits.push({ kind: 'insert', from: '', to, row: i, column: j });
			j--;
		}
	}
	return edits.reverse();
}

function fold(text: string): string {
	symbols(text);
	return text
		.replace(/[A-Z]/g, (letter) => letter.toLowerCase())
		.replace(/[\t\n\v\f\r ]+/g, ' ')
		.replace(/^ | $/g, '');
}

export function prepareName(text: string, expandSaint = true): string {
	const folded = fold(text);
	const key = expandSaint ? folded.replace(/^st\.? /, 'saint ') : folded;
	symbols(key); // Expansion must still fit the documented allocation limit.
	return key;
}

export function parseState(text: string): 'MO' | 'MN' | null {
	const key = fold(text);
	if (key === '') return null;
	if (key === 'mo' || key === 'missouri') return 'MO';
	if (key === 'mn' || key === 'minnesota') return 'MN';
	throw new Error('Use MO/Missouri or MN/Minnesota, or leave state missing.');
}

export type Place = {
	id: string;
	name: string;
	label: string;
	state: 'MO' | 'MN';
	kind: 'county' | 'city';
};
export function directory(): Place[] {
	// Authored stable keys, not official geographic codes. Fresh value records per call.
	return [
		{
			id: 'mo-st-louis-county',
			name: 'St. Louis',
			label: 'St. Louis County, Missouri',
			state: 'MO',
			kind: 'county'
		},
		{
			id: 'mo-st-charles-county',
			name: 'St. Charles',
			label: 'St. Charles County, Missouri',
			state: 'MO',
			kind: 'county'
		},
		{
			id: 'mn-st-louis-county',
			name: 'St. Louis',
			label: 'St. Louis County, Minnesota',
			state: 'MN',
			kind: 'county'
		},
		{
			id: 'mo-st-louis-city',
			name: 'St. Louis',
			label: 'St. Louis city, Missouri',
			state: 'MO',
			kind: 'city'
		}
	];
}
export type Candidate = { place: Place; key: string; distance: number };
export type Review = {
	key: string;
	state: 'MO' | 'MN' | null;
	kind: 'county' | 'city' | null;
	status: 'blank' | 'none' | 'ambiguous' | 'exact' | 'alias' | 'suggestions';
	candidates: Candidate[];
	excluded: { place: Place; reason: string }[];
};

export function review(
	name: string,
	stateText: string,
	kindText: string,
	cutoff: number,
	expandSaint = true
): Review {
	if (!Number.isInteger(cutoff) || cutoff < 0 || cutoff > 8)
		throw new Error('Cutoff must be an integer from 0 through 8.');
	const state = parseState(stateText);
	if (kindText !== '' && kindText !== 'county' && kindText !== 'city')
		throw new Error('Kind must be county, city, or missing.');
	const kind = kindText || null;
	const key = prepareName(name, expandSaint);
	const result: Review = { key, state, kind, status: 'blank', candidates: [], excluded: [] };
	if (!key) return result;
	for (const place of directory()) {
		if (state && place.state !== state) {
			result.excluded.push({ place, reason: 'Different state' });
			continue;
		}
		if (kind && place.kind !== kind) {
			result.excluded.push({ place, reason: 'Different jurisdiction type' });
			continue;
		}
		const candidateKey = prepareName(place.name, expandSaint);
		// Exact prepared keys need no dynamic-programming table.
		const distance = key === candidateKey ? 0 : align(key, candidateKey).distance;
		if (distance <= cutoff) result.candidates.push({ place, key: candidateKey, distance });
	}
	result.candidates.sort(
		(a, b) =>
			a.distance - b.distance || (a.place.id < b.place.id ? -1 : a.place.id > b.place.id ? 1 : 0)
	);
	const first = result.candidates[0];
	if (!first) result.status = 'none';
	else if (!state || !kind || result.candidates[1]?.distance === first.distance)
		result.status = 'ambiguous';
	else if (first.distance === 0) result.status = name === first.place.name ? 'exact' : 'alias';
	else result.status = 'suggestions';
	return result;
}

export function runExample(): void {
	for (const row of [
		{ name: 'ST LOUIS', state: 'MO', kind: 'county' },
		{ name: 'St. Lous', state: 'Missouri', kind: 'county' },
		{ name: 'Saint Louis', state: '', kind: 'county' }
	]) {
		const result = review(row.name, row.state, row.kind, 2);
		console.log(
			result.status +
				'\t' +
				result.candidates.map(({ place, distance }) => `${place.id}:${distance}`).join(',')
		);
		// The caller presents candidates. A reviewer chooses a record before any join.
	}
}

runExample();

package main

import (
	"errors"
	"fmt"
	"sort"
	"strings"
	"unicode/utf8"
)

const MaxSymbols = 64

func symbols(text string) ([]rune, error) {
	if !utf8.ValidString(text) {
		return nil, errors.New("Text must be well-formed Unicode.")
	}
	if utf8.RuneCountInString(text) > MaxSymbols {
		return nil, errors.New("Text is limited to 64 Unicode scalar values.")
	}
	return []rune(text), nil
}

type Edit struct {
	Kind, From, To string
	Row, Column    int
}
type Alignment struct {
	Source, Target []rune
	Table          [][]int
	Distance       int
	Edits          []Edit
}

func Align(sourceText, targetText string) (Alignment, error) {
	source, err := symbols(sourceText)
	if err != nil {
		return Alignment{}, err
	}
	target, err := symbols(targetText)
	if err != nil {
		return Alignment{}, err
	}
	m, n := len(source), len(target)
	table := make([][]int, m+1)
	for i := range table {
		table[i] = make([]int, n+1)
		table[i][0] = i
	}
	for j := 0; j <= n; j++ {
		table[0][j] = j
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			change := 1
			if source[i-1] == target[j-1] {
				change = 0
			}
			table[i][j] = min(
				table[i-1][j]+1,        // delete the trailing source symbol
				table[i][j-1]+1,        // insert the trailing target symbol
				table[i-1][j-1]+change, // keep or replace
			)
		}
	}
	return Alignment{source, target, table, table[m][n], recoverEdits(source, target, table)}, nil
}


// Ties prefer diagonal (keep/replace), then deletion, then insertion.
func recoverEdits(source, target []rune, table [][]int) []Edit {
	edits := []Edit{}
	i, j := len(source), len(target)
	for i > 0 || j > 0 {
		from, to := "", ""
		if i > 0 {
			from = string(source[i-1])
		}
		if j > 0 {
			to = string(target[j-1])
		}
		change := 1
		if from == to {
			change = 0
		}
		if i > 0 && j > 0 && table[i][j] == table[i-1][j-1]+change {
			kind := "replace"
			if change == 0 {
				kind = "keep"
			}
			edits = append(edits, Edit{kind, from, to, i, j})
			i--
			j--
		} else if i > 0 && table[i][j] == table[i-1][j]+1 {
			edits = append(edits, Edit{"delete", from, "", i, j})
			i--
		} else {
			edits = append(edits, Edit{"insert", "", to, i, j})
			j--
		}
	}
	for left, right := 0, len(edits)-1; left < right; left, right = left+1, right-1 {
		edits[left], edits[right] = edits[right], edits[left]
	}
	return edits
}

func fold(text string) (string, error) {
	if _, err := symbols(text); err != nil {
		return "", err
	}
	var out strings.Builder
	space := false
	for _, c := range text {
		if c == ' ' || (c >= '\t' && c <= '\r') {
			space = out.Len() > 0
			continue
		}
		if space {
			out.WriteByte(' ')
			space = false
		}
		if c >= 'A' && c <= 'Z' {
			c += 'a' - 'A'
		}
		out.WriteRune(c)
	}
	return out.String(), nil
}

func PrepareName(text string, expandSaint bool) (string, error) {
	key, err := fold(text)
	if err != nil {
		return "", err
	}
	if expandSaint {
		if strings.HasPrefix(key, "st. ") {
			key = "saint " + key[4:]
		} else if strings.HasPrefix(key, "st ") {
			key = "saint " + key[3:]
		}
	}
	if _, err := symbols(key); err != nil {
		return "", err
	}
	return key, nil
}

func ParseState(text string) (string, error) {
	key, err := fold(text)
	if err != nil {
		return "", err
	}
	switch key {
	case "":
		return "", nil
	case "mo", "missouri":
		return "MO", nil
	case "mn", "minnesota":
		return "MN", nil
	default:
		return "", errors.New("Use MO/Missouri or MN/Minnesota, or leave state missing.")
	}
}


type Place struct{ ID, Name, Label, State, Kind string }

func Directory() []Place {
	// Authored stable keys, not official geographic codes. Fresh value records per call.
	return []Place{
		{"mo-st-louis-county", "St. Louis", "St. Louis County, Missouri", "MO", "county"},
		{"mo-st-charles-county", "St. Charles", "St. Charles County, Missouri", "MO", "county"},
		{"mn-st-louis-county", "St. Louis", "St. Louis County, Minnesota", "MN", "county"},
		{"mo-st-louis-city", "St. Louis", "St. Louis city, Missouri", "MO", "city"},
	}
}

type Candidate struct {
	Place    Place
	Key      string
	Distance int
}
type Excluded struct {
	Place  Place
	Reason string
}
type ReviewResult struct {
	Key, State, Kind, Status string
	Candidates               []Candidate
	Excluded                 []Excluded
}

func Review(name, stateText, kind string, cutoff int, expandSaint bool) (ReviewResult, error) {
	if cutoff < 0 || cutoff > 8 {
		return ReviewResult{}, errors.New("Cutoff must be an integer from 0 through 8.")
	}
	state, err := ParseState(stateText)
	if err != nil {
		return ReviewResult{}, err
	}
	if kind != "" && kind != "county" && kind != "city" {
		return ReviewResult{}, errors.New("Kind must be county, city, or missing.")
	}
	key, err := PrepareName(name, expandSaint)
	if err != nil {
		return ReviewResult{}, err
	}
	result := ReviewResult{key, state, kind, "blank", []Candidate{}, []Excluded{}}
	if key == "" {
		return result, nil
	}
	for _, place := range Directory() {
		if state != "" && place.State != state {
			result.Excluded = append(result.Excluded, Excluded{place, "Different state"})
			continue
		}
		if kind != "" && place.Kind != kind {
			result.Excluded = append(result.Excluded, Excluded{place, "Different jurisdiction type"})
			continue
		}
		candidateKey, err := PrepareName(place.Name, expandSaint)
		if err != nil {
			return ReviewResult{}, err
		}
		distance := 0 // Exact prepared keys need no dynamic-programming table.
		if key != candidateKey {
			alignment, err := Align(key, candidateKey)
			if err != nil {
				return ReviewResult{}, err
			}
			distance = alignment.Distance
		}
		if distance <= cutoff {
			result.Candidates = append(result.Candidates, Candidate{place, candidateKey, distance})
		}
	}
	sort.Slice(result.Candidates, func(i, j int) bool {
		a, b := result.Candidates[i], result.Candidates[j]
		if a.Distance != b.Distance {
			return a.Distance < b.Distance
		}
		return a.Place.ID < b.Place.ID
	})
	if len(result.Candidates) == 0 {
		result.Status = "none"
	} else {
		first := result.Candidates[0]
		if state == "" || kind == "" || (len(result.Candidates) > 1 && result.Candidates[1].Distance == first.Distance) {
			result.Status = "ambiguous"
		} else if first.Distance == 0 {
			result.Status = "alias"
			if name == first.Place.Name {
				result.Status = "exact"
			}
		} else {
			result.Status = "suggestions"
		}
	}
	return result, nil
}


func main() {
	for _, row := range []struct{ Name, State, Kind string }{
		{"ST LOUIS", "MO", "county"},
		{"St. Lous", "Missouri", "county"},
		{"Saint Louis", "", "county"},
	} {
		result, err := Review(row.Name, row.State, row.Kind, 2, true)
		if err != nil {
			fmt.Println(err)
			continue
		}
		matches := []string{}
		for _, candidate := range result.Candidates {
			matches = append(matches, fmt.Sprintf("%s:%d", candidate.Place.ID, candidate.Distance))
		}
		fmt.Printf("%s\t%s\n", result.Status, strings.Join(matches, ","))
		// The caller presents candidates. A reviewer chooses a record before any join.
	}
}