andygrove opened a new issue, #204:
URL: https://github.com/apache/datafusion-spark/issues/204
Part of #177 and apache/datafusion-comet#7300.
### What the function does
`levenshtein(str1, str2[, threshold])` returns the Levenshtein edit distance
between two strings: the minimum number of single-character insertions,
deletions and substitutions. Characters are UTF-8 code points, compared byte
for byte. With the optional `threshold` (since Spark 3.5.0), the function
returns `-1` if the distance is greater than `threshold`. Available since Spark
1.5.0.
`str1` and `str2` are STRING (`StringTypeWithCollation(supportsTrimCollation
= true)`) and `threshold` is INT, all via `ImplicitCastInputTypes`. The return
type is INT. It is null-intolerant: NULL in any argument returns NULL (see the
note on `threshold` below). Calling it with fewer than 2 or more than 3
arguments fails with `WRONG_NUM_ARGS`.
### Examples
```sql
SELECT levenshtein('kitten', 'sitting');
-- 3
SELECT levenshtein('kitten', 'sitting', 2);
-- -1
```
From `StringExpressionsSuite` / `UTF8StringSuite`:
```text
levenshtein('', '') -> 0
levenshtein('', 'a') -> 1
levenshtein('aaapppp', '') -> 7
levenshtein('frog', 'fog') -> 1
levenshtein('fly', 'ant') -> 3
levenshtein('elephant', 'hippo') -> 7
levenshtein('hippo', 'zzzzzzzz') -> 8
levenshtein('千世', 'fog') -> 3
levenshtein('世界千世', '大a界b') -> 4
levenshtein(NULL, '') -> NULL
levenshtein('', '', 0) -> 0
levenshtein('aaapppp', '', 7) -> 7
levenshtein('aaapppp', '', 6) -> -1
levenshtein('elephant', 'hippo', 6) -> -1
levenshtein('a', 'b', 0) -> -1
levenshtein('aa', 'aa', 0) -> 0
levenshtein('aaa', 'bbb', 2) -> -1
levenshtein('aaa', 'bbb', 3) -> 3
levenshtein('aaaaaa', 'b', 10) -> 6
levenshtein('12345', '1234567', 1) -> -1
levenshtein('abc', 'acb', 1) -> -1
levenshtein('hello', 'hallo', 2147483647) -> 1
levenshtein('世界千世', '大a界b', 4) -> 4
```
### Edge cases to test
- NULL `str1` or `str2` returns NULL.
- NULL `threshold`: the generated (codegen) path returns NULL. The
interpreted `eval` unboxes NULL to `0`, so it computes with threshold 0
instead. Codegen is the normal path, so return NULL. This was derived from
reading `Levenshtein.eval` and `genCodeWithThreshold`.
- A distance exactly equal to `threshold` returns the distance; a distance
of `threshold + 1` returns `-1`.
- `threshold = 0` with equal strings returns 0; with different strings it
returns `-1`.
- Negative `threshold` always returns `-1`, even for two empty strings (`n
== 0` returns `m <= threshold ? m : -1`). This was derived from the code.
- A large `threshold` (`Integer.MAX_VALUE`) must not overflow. Spark guards
`j + 1 + threshold` explicitly.
- A length difference greater than `threshold` returns `-1` early.
- Empty strings on either side.
- Multi-byte and supplementary characters: one code point is one edit.
Combining sequences count as several code points. Not graphemes.
- Implicit casts: numeric arguments are cast to STRING (`levenshtein(123,
124)`). A string `threshold` that is not a number fails with
`CAST_INVALID_INPUT` under ANSI mode (the default since 4.0).
- Literal and column variants for each argument, including a column
`threshold`.
- Collations (4.0+): any collation is accepted, but the distance is always
computed on raw code points. Collation does not affect the result. Two
conflicting explicit collations is an analysis error.
### Differences across Spark versions
- 3.4: only the 2-argument form (`BinaryExpression`); there is no
`threshold`.
- 3.5: adds the optional `threshold` argument and returns `-1` when it is
exceeded.
- 4.0: collation-aware input types; ANSI is on by default (this affects the
cast of `threshold`). Distance semantics are unchanged.
- 4.1 / 4.2: none found.
### Implementation notes
- Spark source:
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/stringExpressions.scala`
(`Levenshtein`). Kernels: `UTF8String.levenshteinDistance(UTF8String)` and
`levenshteinDistance(UTF8String, int)` in
`common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java`.
These are adapted from commons-text `LevenshteinDistance.unlimitedCompare` /
`limitedCompare`.
- DataFusion core has `levenshtein`
(`datafusion/functions/src/string/levenshtein.rs`, using
`datafusion_common::utils::datafusion_strsim`). It works on `char`s, so its
2-argument results should match Spark. Differences:
- it has no `threshold` argument;
- it returns Int64 for `LargeUtf8`, while Spark always returns INT.
The 2-argument path can delegate to core (casting the result to Int32).
The 3-argument path needs a bounded version. Computing the full distance and
comparing it with `threshold` gives the same results as Spark's banded
algorithm, but is slower for large inputs.
- Module: `crates/spark/src/function/string/levenshtein.rs`.
- Tests: `crates/sqllogictest/test_files/string/levenshtein.slt` exists with
commented-out queries. Enable them and add the threshold boundary cases above.
Document with `#[user_doc]`.
---
_This issue was generated by an LLM (Claude) from the Apache Spark source
code and tests. Examples come from Spark's `ExpressionDescription` examples,
test suites and `.sql.out` golden files, but please verify them against Spark
before relying on them._
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]