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]

Reply via email to