damerau_levenshtein

Applies to VAST Cluster 5.5.

Functions › Text basics › Similarity. Returns the Damerau-Levenshtein edit distance between two strings: like levenshtein, but swapping two neighbouring units counts as one edit, not two. It has no aliases.

Syntax

damerau_levenshtein(a, b)

Argument	Type	Description
`a`	`VARCHAR`	The first string.
`b`	`VARCHAR`	The string to compare it with.

Returns: BIGINT.

Aliases: none.

Set up the examples

The examples connect with the ADBC driver, as in VAST Query Engine (ADBC), and work in a schema called docs_sql_fn_damerau_levenshtein. Set QE_ENDPOINT, AWS_ACCESS_KEY_ID, AWS_SECRET_ACCESS_KEY and VASTDB_BUCKET (SQL reference), and run the blocks in order in one Python session. Below each block is the output you should see.

This block connects, defines the run() and plan() helpers, and creates a table of product names as customers typed them into a search box. The last row has no value:

import os
import re

import adbc_driver_manager
import adbc_driver_manager.dbapi as dbapi
import adbc_driver_vastdb

BUCKET = os.environ["VASTDB_BUCKET"]
SCHEMA = f'"{BUCKET}/docs_sql_fn_damerau_levenshtein"'

conn = dbapi.connect(
    driver=adbc_driver_vastdb.get_driver_path(),
    db_kwargs={
        "vast.db.endpoint": os.environ["QE_ENDPOINT"],
        "vast.db.access_key": os.environ["AWS_ACCESS_KEY_ID"],
        "vast.db.secret_key": os.environ["AWS_SECRET_ACCESS_KEY"],
    },
    autocommit=True,
)

def server_message(e):
    """The server's message in a driver error, without the request ID or the echoed statement."""
    text = re.sub(r"\[req=0x[0-9a-f]+\]: ", "", str(e))
    found = (re.search(r'message: "(.*?)", request_id', text, re.S)
             or re.search(r"description: (.*)\)", text, re.S))
    message = found.group(1) if found else text.strip().splitlines()[-1]
    message = re.sub(r"^Plan query: '.*?' failed with: ", "", message, flags=re.S)
    message = re.split(r"\\n|\n", message)[0].replace('\\"', '"')
    return message.replace(BUCKET, "<bucket>")

def run(sql):
    """Run one statement. Print the rows it returns, or the error."""
    try:
        with conn.cursor() as cur:
            cur.execute(sql)
            rows = cur.fetchall() if cur.description else []
    except (adbc_driver_manager.Error, OSError) as e:
        print(f"{type(e).__name__}: {server_message(e)}")
    else:
        print(rows)

def plan(sql):
    """Print the plan without its ~N Rows lines: the table's row count, which can still be 0 just after an insert."""
    with conn.cursor() as cur:
        cur.execute("EXPLAIN " + sql)
        steps = cur.fetchall()[0][1]
    print("\n".join(line for line in steps.splitlines() if "Rows" not in line))

TABLE = f"{SCHEMA}.searches"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, term VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'keyboard'), "
    "(2, 'keybaord'), "
    "(3, 'kyeboard'), "
    "(4, 'keyborad'), "
    "(5, 'monitor'), "
    "(6, NULL)")

[]
[]
[(6,)]

What it does

damerau_levenshtein counts the edits needed to turn a into b. Each edit costs 1 and is one of:

inserting one unit,
deleting one unit,
replacing one unit with another,
swapping two neighbouring units (a transposition).

The last kind is what makes it different from levenshtein, which needs two substitutions for a swap. That suits typing mistakes such as teh for the.

Call	Result	Why
`damerau_levenshtein('ab', 'ba')`	`1`	one swap (`levenshtein` gives `2`)
`damerau_levenshtein('abcd', 'acbd')`	`1`	the swapped pair is in the middle
`damerau_levenshtein('ca', 'abc')`	`2`	swap to `ac`, then insert `b` between the swapped characters
`damerau_levenshtein('', 'ab')`	`2`	against an empty string, the distance is the length of the other string
`damerau_levenshtein('kitten', 'sitting')`	`3`	no swaps help, so it's the same as `levenshtein`

It compares UTF-8 bytes, not characters, as levenshtein does: a letter outside ASCII takes two or more bytes, and each byte is edited on its own. The string 'e\u0301 🇫🇷 ẞ' is 7 code points but 16 bytes, and its distance from 'Hlelo' is 16. With a precomposed é (two bytes), damerau_levenshtein('café', 'cafe') is 2, not 1, and damerau_levenshtein('é', 'è') is 1, because only the second bytes differ. To compare accented text by letters, remove the accents first with strip_accents.

NULLs and edge cases

Input	Result
`NULL` as either argument	`NULL`
`''` and `'Hlelo'`	`5`
`'ab'` and `'ba'`	`1`
`'ca'` and `'abc'`	`2`
`'e\u0301 🇫🇷 ẞ'` and `'Hlelo'`	`16`
A number, decimal, date, boolean, `BLOB` or list	Error: `No function matches the given name and argument types`

The same cases, as the cluster returns them. They use the table and helpers from Set up the examples:

run("SELECT damerau_levenshtein(NULL, 'Hlelo'), damerau_levenshtein('a', NULL), "
    "damerau_levenshtein('', 'Hlelo'), damerau_levenshtein('ab', 'ba'), damerau_levenshtein('ca', 'abc')")
run("SELECT damerau_levenshtein('e\u0301 🇫🇷 ẞ', 'Hlelo')")
run("SELECT damerau_levenshtein(123, 'Hlelo')")

[(None, None, 5, 1, 2)]
[(16,)]
InternalError: Binder Error: No function matches the given name and argument types 'damerau_levenshtein(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.

Examples

Each search term against the product name keyboard, with both distances. Each of rows 2 to 4 has two neighbouring letters swapped: one edit for damerau_levenshtein, two for levenshtein:

run(f"SELECT id, term, damerau_levenshtein(term, 'keyboard'), levenshtein(term, 'keyboard') "
    f"FROM {TABLE} ORDER BY id LIMIT 10")

[(1, 'keyboard', 0, 0), (2, 'keybaord', 1, 2), (3, 'kyeboard', 1, 2), (4, 'keyborad', 1, 2), (5, 'monitor', 7, 7), (6, None, None, None)]

Keep the searches that are at most one typing mistake away from keyboard:

run(f"SELECT id, term FROM {TABLE} WHERE damerau_levenshtein(term, 'keyboard') <= 1 ORDER BY id LIMIT 10")

[(1, 'keyboard'), (2, 'keybaord'), (3, 'kyeboard'), (4, 'keyborad')]

How it runs in VAST

The Query Engine runs on the cluster's CNodes, and a query on a table starts with a scan in VAST DataBase (VAST_SCAN). VAST DataBase can evaluate a comparison of a column with a constant, but not a function of a column, so damerau_levenshtein() is always computed by the Query Engine:

In the SELECT list, the scan reads the column and the Query Engine computes damerau_levenshtein() for each row it returns.
In WHERE, the scan sends the column for every row, and a FILTER step in the Query Engine computes damerau_levenshtein() and keeps the rows that match. No rows are skipped in storage.

The plan of the WHERE example shows the FILTER step above the scan:

plan(f"SELECT id FROM {TABLE} WHERE damerau_levenshtein(term, 'keyboard') <= 1")

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #1            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ (damerau_levenshtein(term,│
│      'keyboard') <= 1)    │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            term           │
│             id            │
│                           │
└───────────────────────────┘

Make it faster

Narrow the rows with a pushed-down condition first. A comparison of a raw column with a constant is evaluated in VAST DataBase, so only the rows that pass it reach damerau_levenshtein(). In id > 100 AND damerau_levenshtein(term, 'keyboard') <= 1, id > 100 is evaluated in storage.
Look up exact matches without it. term = 'keyboard' is pushed down; damerau_levenshtein(term, 'keyboard') = 0 gives the same rows but runs on every row. The plan for term = 'keyboard' has no FILTER step:

plan(f"SELECT id FROM {TABLE} WHERE term = 'keyboard'")

┌───────────────────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│      Projections: id      │
│                           │
└───────────────────────────┘

Limitations and errors

Strings only. A number, decimal, date, boolean, BLOB or list fails with No function matches the given name and argument types. Cast it first: damerau_levenshtein(CAST(n AS VARCHAR), '123').
Bytes, not characters. Accented and other non-ASCII letters count as more than one unit. See What it does.
Case-sensitive. damerau_levenshtein('Keyboard', 'keyboard') is 1. To ignore case, compare lower() of both strings. This block compares 'Keyboard' with and without lower():

run("SELECT damerau_levenshtein(123, 'Hlelo')")
run("SELECT damerau_levenshtein('Keyboard', 'keyboard'), damerau_levenshtein(lower('Keyboard'), 'keyboard')")

InternalError: Binder Error: No function matches the given name and argument types 'damerau_levenshtein(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.
[(1, 0)]

Similar functions

Function	Measures	`'ab'` and `'ba'`	`'kitten'` and `'sitting'`
`damerau_levenshtein`	edit distance; a swap of neighbours is one edit	`1`	`3`
levenshtein (also `editdist3`)	edit distance; a swap is two edits	`2`	`3`
jaccard	distinct bytes the strings share, as a share of all their distinct bytes, from 0 to 1; order is ignored	`1.0`	`0.42857142857142855`
jaro_similarity	similarity from 0 to 1, based on matching bytes and transpositions	(see its page)	`0.746031746031746`
hamming	byte positions that differ; the strings must be the same length in bytes	(see its page)	`2` (for `'kitten'` and `'sittin'`)

run("SELECT damerau_levenshtein('ab', 'ba'), levenshtein('ab', 'ba'), jaccard('ab', 'ba')")
run("SELECT damerau_levenshtein('kitten', 'sitting'), levenshtein('kitten', 'sitting'), "
    "jaccard('kitten', 'sitting'), jaro_similarity('kitten', 'sitting'), hamming('kitten', 'sittin')")

[(1, 2, 1.0)]
[(3, 3, 0.42857142857142855, 0.746031746031746, 2)]

Clean up:

run(f"DROP TABLE IF EXISTS {TABLE}")
run(f"DROP SCHEMA IF EXISTS {SCHEMA}")
conn.close()

[]
[]