diff options
| author | akinshchikov <akinshchikov@yandex-team.com> | 2023-07-03 12:26:39 +0300 |
|---|---|---|
| committer | akinshchikov <akinshchikov@yandex-team.com> | 2023-07-03 12:26:39 +0300 |
| commit | 72c25e282d527a441d02f56820179cd6990010d1 (patch) | |
| tree | c6dea4e7c15241f83584fce9c27917054af01e04 /library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp | |
| parent | f12bd19e8cddac19aed1767a20500459bdd2feb5 (diff) | |
| download | ydb-72c25e282d527a441d02f56820179cd6990010d1.tar.gz | |
Replace the functions for the `Levenshtein` and the `Damerau–Levenshtein` distances with the memory effective version.
YQL UDFs `String::LevensteinDistance` and `Unicode::LevensteinDistance` use `NLevenshtein::Distance` inside.
The previous version of `NLevenshtein::Distance` uses O(nm) space instead of O(min(n, m)).
Diffstat (limited to 'library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp')
| -rw-r--r-- | library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp | 11 |
1 files changed, 11 insertions, 0 deletions
diff --git a/library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp b/library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp index 67c0f1da6f..6256a841c2 100644 --- a/library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp +++ b/library/cpp/string_utils/levenshtein_diff/levenshtein_diff_ut.cpp @@ -26,9 +26,20 @@ namespace { Y_UNIT_TEST_SUITE(Levenstein) { Y_UNIT_TEST(Distance) { + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::Distance(TStringBuf("knight"), TStringBuf("king")), 4); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::Distance(TStringBuf("life flies"), TStringBuf("fly lives")), 6); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::Distance(TStringBuf("spot trail"), TStringBuf("stop trial")), 4); UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::Distance(TStringBuf("hello"), TStringBuf("hulloah")), 3); UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::Distance(TStringBuf("yeoman"), TStringBuf("yo man")), 2); } + + Y_UNIT_TEST(DamerauDistance) { + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::DamerauDistance(TStringBuf("knight"), TStringBuf("king")), 3); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::DamerauDistance(TStringBuf("life flies"), TStringBuf("fly lives")), 6); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::DamerauDistance(TStringBuf("spot trail"), TStringBuf("stop trial")), 3); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::DamerauDistance(TStringBuf("status"), TStringBuf("tsatus")), 1); + UNIT_ASSERT_VALUES_EQUAL(NLevenshtein::DamerauDistance(TStringBuf("hello"), TStringBuf("heh lol")), 3); + } } Y_UNIT_TEST_SUITE(WeightedLevenstein) { |