Edit distance

Edit distance is the minimum total cost of changing one string into another using a specified set of edits. When a trade file contains an unfamiliar instrument label, the distance can help an analyst shortlist records to inspect before joining prices or positions to the file.

In standard Levenshtein distance, inserting, deleting or substituting a single character costs one. Keeping a matching character costs zero. For the fictional strings BID1 and BDI2, the distance is 3. Three substitutions suffice. Two substitutions can fix at most two of the three mismatched positions. A deletion and an insertion would preserve at least three original characters in order, but these strings share only B, I and D, and I and D occur in opposite orders. Wagner and Fischer (1974), The String-to-String Correction Problem

Allow a swap of two adjacent characters at cost one, alongside the same three unit-cost edits, and the answer becomes 2. Swap ID to get BDI1, then replace 1 with 2. A swap alone leaves the digit unchanged, and a single substitution leaves the reversal unresolved. This convention is unrestricted Damerau–Levenshtein distance, which allows adjacent swaps anywhere in the edit sequence. Lowrance and Wagner (1975), An Extension of the String-to-String Correction Problem

Let $D_{i,j}$ be the minimum edit cost to turn the first $i$ characters of source $x$ into the first $j$ characters of target $y$. The empty-prefix edges are $D_{i,0}=i$ and $D_{0,j}=j$. At each interior cell, dynamic programming reuses three smaller prefix costs.

The three terms delete $x_i$, insert $y_j$, or align the two characters and charge one only if they differ. At row BI and column BDI, matching the last I carries over the cost of one from B to BD. Filling the table left to right and top to bottom gives $D_{4,4}=3$. For strings of lengths $m$ and $n$, the table takes $O(mn)$ time when both lengths are positive. Wagner and Fischer (1974), section 4

Suppose BID2 is another candidate for BID1. Its distance is one under either rule, so it ranks ahead of BDI2. If its listing venue or share class conflicts with the trade record, the smaller score gives no basis for choosing it. Even identical ticker text can refer to different instruments across venues or dates.

Check the candidate against reference data for the date on the record. Use the identifier scheme, venue and relevant instrument fields, such as share class or futures contract expiry, to resolve the match. Keep the record unresolved for review if the reference fields cannot identify a single instrument. OpenFIGI’s mapping endpoint illustrates why those fields matter by accepting identifier types and filters such as market identification code and currency, and by allowing multiple results per query. OpenFIGI, v3 Mapping API documentation

The SelfMadeQuant lesson Instrument Data Conventions covers how ticker reuse and venue and share-class differences cause mapping failures. The full lesson requires membership.