Posted By

devnull69 on 04/12/12


Tagged

levenshtein


Versions (?)

Levenshtein for Javascript


 / Published in: JavaScript
 

Calculates the levenshtein distance between two strings

  1. function levenshtein (s1, s2) {
  2. // Calculate Levenshtein distance between two strings
  3. //
  4. // version: 1109.2015
  5. // discuss at: http://phpjs.org/functions/levenshtein // + original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
  6. // + bugfixed by: Onno Marsman
  7. // + revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
  8. // + reimplemented by: Brett Zamir (http://brett-zamir.me)
  9. // + reimplemented by: Alexander M Beedie // * example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
  10. // * returns 1: 3
  11. if (s1 == s2) {
  12. return 0;
  13. }
  14. var s1_len = s1.length;
  15. var s2_len = s2.length;
  16. if (s1_len === 0) {
  17. return s2_len;
  18. }
  19. if (s2_len === 0) {
  20. return s1_len;
  21. }
  22. // BEGIN STATIC
  23. var split = false;
  24. try {
  25. split = !('0')[0];
  26. } catch (e) {
  27. split = true; // Earlier IE may not support access by string index
  28. }
  29. // END STATIC
  30. if (split) {
  31. s1 = s1.split('');
  32. s2 = s2.split('');
  33. }
  34.  
  35. var v0 = new Array(s1_len + 1);
  36. var v1 = new Array(s1_len + 1);
  37. var s1_idx = 0,
  38. s2_idx = 0,
  39. cost = 0;
  40. for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
  41. v0[s1_idx] = s1_idx;
  42. }
  43. var char_s1 = '',
  44. char_s2 = '';
  45. for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {
  46. v1[0] = s2_idx;
  47. char_s2 = s2[s2_idx - 1];
  48.  
  49. for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {
  50. char_s1 = s1[s1_idx];
  51. cost = (char_s1 == char_s2) ? 0 : 1;
  52. var m_min = v0[s1_idx + 1] + 1;
  53. var b = v1[s1_idx] + 1;
  54. var c = v0[s1_idx] + cost;
  55. if (b < m_min) {
  56. m_min = b;
  57. }
  58. if (c < m_min) {
  59. m_min = c;
  60. }
  61. v1[s1_idx + 1] = m_min;
  62. }
  63. var v_tmp = v0;
  64. v0 = v1;
  65. v1 = v_tmp;
  66. }
  67. return v0[s1_len];
  68. }

Report this snippet  

You need to login to post a comment.