ascii-chat
Binary v0.16.50-198-g78f51665f
Library lib/v0.3.2-2240-g78f51665f
Video chat in your terminal
Loading...
Searching...
No Matches
levenshtein.c
Go to the documentation of this file.
1
11
12#include <string.h>
13#include <stdlib.h>
14#include <stdint.h>
17#include <ascii-chat/common.h>
18#include <defer.h>
19
20// Returns a size_t, depicting the difference between `a` and `b`.
21// See <https://en.wikipedia.org/wiki/Levenshtein_distance> for more information.
22// Works with UTF-8 strings by comparing codepoints instead of bytes.
23size_t levenshtein_n(const char *a, const size_t length, const char *b, const size_t bLength) {
24 // Shortcut optimizations / degenerate cases.
25 if (a == b) {
26 return 0;
27 }
28
29 if (length == 0) {
30 return bLength;
31 }
32
33 if (bLength == 0) {
34 return length;
35 }
36
37 size_t *cache = SAFE_CALLOC(length, sizeof(size_t), size_t *);
38 if (!cache) {
39 return SIZE_MAX; // Allocation failed
40 }
41
42 size_t index = 0;
43 size_t bIndex = 0;
44 size_t distance;
45 size_t bDistance;
46 size_t result = 0;
47 char code;
48
49 // initialize the vector.
50 while (index < length) {
51 cache[index] = index + 1;
52 index++;
53 }
54
55 // Loop.
56 while (bIndex < bLength) {
57 code = b[bIndex];
58 result = distance = bIndex++;
59
60 for (index = 0; index < length; index++) {
61 bDistance = code == a[index] ? distance : distance + 1;
62 distance = cache[index];
63
64 cache[index] = result = distance > result ? bDistance > result ? result + 1 : bDistance : bDistance > distance ? distance + 1 : bDistance;
65 }
66 }
67
68 SAFE_FREE(cache);
69
70 return result;
71}
72
73size_t levenshtein(const char *a, const char *b) {
74 if (!a || !b) {
75 return SIZE_MAX;
76 }
77
78 // Count UTF-8 characters instead of bytes
79 size_t char_count_a = utf8_char_count(a);
80 size_t char_count_b = utf8_char_count(b);
81
82 if (char_count_a == SIZE_MAX || char_count_b == SIZE_MAX) {
83 return SIZE_MAX; // Invalid UTF-8 in one of the strings
84 }
85
86 // Convert strings to codepoint arrays for UTF-8-aware comparison
87 if (char_count_a == 0) {
88 return char_count_b;
89 }
90 if (char_count_b == 0) {
91 return char_count_a;
92 }
93
94 SAFE_MALLOC_DEFER_FREE(codepoints_a, char_count_a * sizeof(uint32_t), uint32_t *);
95 SAFE_MALLOC_DEFER_FREE(codepoints_b, char_count_b * sizeof(uint32_t), uint32_t *);
96
97 if (!codepoints_a || !codepoints_b) {
98 return SIZE_MAX;
99 }
100
101 size_t decoded_a = utf8_to_codepoints(a, codepoints_a, char_count_a);
102 size_t decoded_b = utf8_to_codepoints(b, codepoints_b, char_count_b);
103
104 if (decoded_a == SIZE_MAX || decoded_b == SIZE_MAX) {
105 return SIZE_MAX;
106 }
107
108 // Compute Levenshtein distance on codepoint arrays
109 SAFE_CALLOC_DEFER_FREE(cache, char_count_a * sizeof(size_t), 1, size_t *);
110 if (!cache) {
111 return SIZE_MAX;
112 }
113
114 // Initialize cache
115 for (size_t i = 0; i < char_count_a; i++) {
116 cache[i] = i + 1;
117 }
118
119 size_t distance = 0;
120 size_t result = 0;
121 for (size_t b_idx = 0; b_idx < char_count_b; b_idx++) {
122 uint32_t b_code = codepoints_b[b_idx];
123 result = distance = b_idx;
124
125 for (size_t a_idx = 0; a_idx < char_count_a; a_idx++) {
126 uint32_t a_code = codepoints_a[a_idx];
127 size_t b_distance = (a_code == b_code) ? distance : distance + 1;
128 distance = cache[a_idx];
129
130 cache[a_idx] = result = (distance > result) ? ((b_distance > result) ? result + 1 : b_distance) : ((b_distance > distance) ? distance + 1 : b_distance);
131 }
132 }
133
134 return result;
135}
136
137const char *levenshtein_find_similar(const char *unknown, const char *const *candidates) {
138 if (!unknown || !candidates) {
139 return NULL;
140 }
141
142 const char *best_match = NULL;
143 size_t best_distance = SIZE_MAX;
144
145 for (int i = 0; candidates[i] != NULL; i++) {
146 size_t dist = levenshtein(unknown, candidates[i]);
147 if (dist < best_distance) {
148 best_distance = dist;
149 best_match = candidates[i];
150 }
151 }
152
153 // Only suggest if the distance is within our threshold
154 if (best_distance <= LEVENSHTEIN_SUGGESTION_THRESHOLD) {
155 return best_match;
156 }
157
158 return NULL;
159}
unsigned int uint32_t
#define SAFE_FREE(ptr)
#define SAFE_MALLOC_DEFER_FREE(name, size, cast)
#define SAFE_CALLOC(count, size, cast)
#define SAFE_CALLOC_DEFER_FREE(name, count, size, cast)
size_t levenshtein_n(const char *a, const size_t length, const char *b, const size_t bLength)
Calculate Levenshtein distance with explicit string lengths.
Definition levenshtein.c:23
const char * levenshtein_find_similar(const char *unknown, const char *const *candidates)
Find the most similar string from a NULL-terminated array.
size_t levenshtein(const char *a, const char *b)
Calculate Levenshtein distance between two strings.
Definition levenshtein.c:73
#define LEVENSHTEIN_SUGGESTION_THRESHOLD
Maximum edit distance to suggest an option.
Definition levenshtein.h:32
size_t utf8_to_codepoints(const char *str, uint32_t *out_codepoints, size_t max_codepoints)
Convert UTF-8 string to array of Unicode codepoints.
Definition utf8.c:157
size_t utf8_char_count(const char *str)
Count UTF-8 characters (not bytes).
Definition utf8.c:108
⚙️ Common definitions, error codes, macros, and types shared throughout the application
Levenshtein distance algorithm for fuzzy string matching.
static bool size_t index
Definition queries.h:8
🔤 String Manipulation and Shell Escaping Utilities
🔤 UTF-8 Encoding and Decoding Utilities