MCPcopy Create free account
hub / github.com/apache/arrow / levenshtein

Function levenshtein

cpp/src/gandiva/precompiled/string_ops.cc:1763–1864  ·  view source on GitHub ↗

Calculate the levenshtein distance between two string values

Source from the content-addressed store, hash-verified

1761
1762// Calculate the levenshtein distance between two string values
1763FORCE_INLINE
1764gdv_int32 levenshtein(int64_t context, const char* in1, int32_t in1_len, const char* in2,
1765 int32_t in2_len) {
1766 if (in1_len < 0 || in2_len < 0) {
1767 char err_msg[128];
1768 snprintf(err_msg, sizeof(err_msg),
1769 "LEVENSHTEIN: input lengths must be non-negative, got %d and %d", in1_len,
1770 in2_len);
1771 gdv_fn_context_set_error_msg(context, err_msg);
1772 return 0;
1773 }
1774
1775 // Check input size 0
1776 if (in1_len == 0) {
1777 return in2_len;
1778 }
1779 if (in2_len == 0) {
1780 return in1_len;
1781 }
1782
1783 // arr_larger and arr_smaller is one pointer for entries
1784 const char* arr_larger;
1785 const char* arr_smaller;
1786 // len_larger and len_smaller is one copy from lengths
1787 int len_larger;
1788 int len_smaller;
1789
1790 if (in1_len < in2_len) {
1791 len_larger = in2_len;
1792 arr_larger = in2;
1793
1794 len_smaller = in1_len;
1795 arr_smaller = in1;
1796 } else {
1797 len_larger = in1_len;
1798 arr_larger = in1;
1799
1800 len_smaller = in2_len;
1801 arr_smaller = in2;
1802 }
1803
1804 int* ptr = reinterpret_cast<int*>(
1805 gdv_fn_context_arena_malloc(context, (len_smaller + 1) * 2 * sizeof(int)));
1806 if (ptr == nullptr) {
1807 gdv_fn_context_set_error_msg(context,
1808 "LEVENSHTEIN: could not allocate working memory");
1809 return 0;
1810 }
1811
1812 // MEMORY ADDRESS MALLOC
1813 // v0 -> (0, ..., &ptr[in2_len])
1814 // v1 -> (in2_len+1, ..., &ptr[in2_len * 2])
1815 int* v0;
1816 int* v1;
1817 int* aux;
1818 v0 = &ptr[0];
1819 v1 = &ptr[len_smaller + 1];
1820

Callers 1

TESTFunction · 0.85

Calls 2

Tested by 1

TESTFunction · 0.68