| 1824 | } |
| 1825 | |
| 1826 | IntVal StringFunctions::DamerauLevenshtein( |
| 1827 | FunctionContext* ctx, const StringVal& s1, const StringVal& s2) { |
| 1828 | // Based on https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance |
| 1829 | // Implements restricted Damerau-Levenshtein (optimal string alignment) |
| 1830 | |
| 1831 | int s1len = s1.len; |
| 1832 | int s2len = s2.len; |
| 1833 | |
| 1834 | // error if either input exceeds 255 characters |
| 1835 | if (s1len > 255 || s2len > 255) { |
| 1836 | ctx->SetError("damerau-levenshtein argument exceeds maximum length of 255 " |
| 1837 | "characters"); |
| 1838 | return IntVal(-1); |
| 1839 | } |
| 1840 | |
| 1841 | // short cut cases: |
| 1842 | // - null strings |
| 1843 | // - zero length strings |
| 1844 | // - identical length and value strings |
| 1845 | if (s1.is_null || s2.is_null) return IntVal::null(); |
| 1846 | if (s1len == 0) return IntVal(s2len); |
| 1847 | if (s2len == 0) return IntVal(s1len); |
| 1848 | if (s1len == s2len && memcmp(s1.ptr, s2.ptr, s1len) == 0) return IntVal(0); |
| 1849 | |
| 1850 | int i; |
| 1851 | int j; |
| 1852 | int l_cost; |
| 1853 | int ptr_array_length = sizeof(int*) * (s1len + 1); |
| 1854 | int int_array_length = sizeof(int) * (s2len + 1) * (s1len + 1); |
| 1855 | |
| 1856 | // Allocating a 2D array (with d being an array of pointers to the start of the rows) |
| 1857 | int** d = reinterpret_cast<int**>(ctx->Allocate(ptr_array_length)); |
| 1858 | if (UNLIKELY(d == nullptr)) { |
| 1859 | DCHECK(!ctx->impl()->state()->GetQueryStatus().ok()); |
| 1860 | return IntVal::null(); |
| 1861 | } |
| 1862 | int* rows = reinterpret_cast<int*>(ctx->Allocate(int_array_length)); |
| 1863 | if (UNLIKELY(rows == nullptr)) { |
| 1864 | ctx->Free(reinterpret_cast<uint8_t*>(d)); |
| 1865 | DCHECK(!ctx->impl()->state()->GetQueryStatus().ok()); |
| 1866 | return IntVal::null(); |
| 1867 | } |
| 1868 | // Setting the pointers in the pointer-array to the start of (s2len + 1) length |
| 1869 | // intervals and initializing its values based on the mentioned algorithm. |
| 1870 | for (i = 0; i <= s1len; ++i) { |
| 1871 | d[i] = rows + (s2len + 1) * i; |
| 1872 | d[i][0] = i; |
| 1873 | } |
| 1874 | std::iota(d[0], d[0] + s2len + 1, 0); |
| 1875 | |
| 1876 | for (i = 1; i <= s1len; ++i) { |
| 1877 | for (j = 1; j <= s2len; ++j) { |
| 1878 | if (s1.ptr[i - 1] == s2.ptr[j - 1]) { |
| 1879 | l_cost = 0; |
| 1880 | } else { |
| 1881 | l_cost = 1; |
| 1882 | } |
| 1883 | d[i][j] = std::min(d[i - 1][j - 1] + l_cost, // substitution |