| 488 | } |
| 489 | |
| 490 | pub fn levenshtein_distance(a: &[u8], b: &[u8], max_cost: usize) -> usize { |
| 491 | if a == b { |
| 492 | return 0; |
| 493 | } |
| 494 | |
| 495 | let (mut a_bytes, mut b_bytes) = (a, b); |
| 496 | let (mut a_begin, mut a_end) = (0usize, a.len()); |
| 497 | let (mut b_begin, mut b_end) = (0usize, b.len()); |
| 498 | |
| 499 | while a_end > 0 && b_end > 0 && (a_bytes[a_begin] == b_bytes[b_begin]) { |
| 500 | a_begin += 1; |
| 501 | b_begin += 1; |
| 502 | a_end -= 1; |
| 503 | b_end -= 1; |
| 504 | } |
| 505 | while a_end > 0 |
| 506 | && b_end > 0 |
| 507 | && (a_bytes[a_begin + a_end - 1] == b_bytes[b_begin + b_end - 1]) |
| 508 | { |
| 509 | a_end -= 1; |
| 510 | b_end -= 1; |
| 511 | } |
| 512 | if a_end == 0 || b_end == 0 { |
| 513 | return (a_end + b_end) * MOVE_COST; |
| 514 | } |
| 515 | if a_end > MAX_STRING_SIZE || b_end > MAX_STRING_SIZE { |
| 516 | return max_cost + 1; |
| 517 | } |
| 518 | |
| 519 | if b_end < a_end { |
| 520 | core::mem::swap(&mut a_bytes, &mut b_bytes); |
| 521 | core::mem::swap(&mut a_begin, &mut b_begin); |
| 522 | core::mem::swap(&mut a_end, &mut b_end); |
| 523 | } |
| 524 | |
| 525 | if (b_end - a_end) * MOVE_COST > max_cost { |
| 526 | return max_cost + 1; |
| 527 | } |
| 528 | |
| 529 | let mut buffer = [0usize; MAX_STRING_SIZE]; |
| 530 | |
| 531 | for (i, x) in buffer.iter_mut().take(a_end).enumerate() { |
| 532 | *x = (i + 1) * MOVE_COST; |
| 533 | } |
| 534 | |
| 535 | let mut result = 0usize; |
| 536 | for (b_index, b_code) in b_bytes[b_begin..(b_begin + b_end)].iter().enumerate() { |
| 537 | result = b_index * MOVE_COST; |
| 538 | let mut distance = result; |
| 539 | let mut minimum = usize::MAX; |
| 540 | for (a_index, a_code) in a_bytes[a_begin..(a_begin + a_end)].iter().enumerate() { |
| 541 | let substitute = distance + substitution_cost(*b_code, *a_code); |
| 542 | distance = buffer[a_index]; |
| 543 | let insert_delete = usize::min(result, distance) + MOVE_COST; |
| 544 | result = usize::min(insert_delete, substitute); |
| 545 | |
| 546 | buffer[a_index] = result; |
| 547 | if result < minimum { |