[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[原创] vbs 实现 LD 算法

本帖最后由 lxzzr 于 2014-7-12 19:54 编辑

LD算法(Levenshtein Distance)又成为编辑距离算法(Edit Distance)。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。

通俗点讲就是比较两个字符串的相似程度。

http://www.enun.net/?p=2442
  1. '======================
  2. '   A   t   e   s   t
  3. ' B 0   1   2   3   4
  4. '
  5. ' e 1   1   1   2   3
  6. '
  7. ' s 2   2   2   1   2
  8. '
  9. ' t 3   2   3   2   1
  10. '======================
  11. Wscript.Echo GetLevenshteinDistince("test", "est")
  12. '==============================================================
  13. ' Copyright (c) enun-net. All rights reserved.
  14. ' ScriptName: GetStrLD.vbs
  15. ' Creation Date: 10/11/2013
  16. ' Last Modified: 10/11/2013
  17. ' Author: 0x22e09
  18. ' Homepage: www.enun.net
  19. ' E-mail: 0x22e09@sina.com
  20. ' Description: Levenshtein Distance.
  21. '==============================================================
  22. Function GetLevenshteinDistince(str1, str2)
  23. Dim x, y, A, B, C, K
  24. Dim Matrix()
  25. ReDim Matrix(Len(str2), Len(str1))
  26. '初始化第一行和第一列
  27. For x = 0 To UBound(Matrix, 1)
  28. Matrix(x, 0) = x
  29. Next
  30. For y = 0 To UBound(Matrix, 2)
  31. Matrix(0, y) = y
  32. Next
  33. '填充矩阵
  34. For x = 1 To UBound(Matrix, 1)
  35. For y = 1 To UBound(Matrix, 2)
  36. If (Mid(str1, Matrix(0, y), 1) = Mid(str2, Matrix(x, 0), 1)) Then
  37. C = Matrix(x -1 ,y - 1)
  38. Else
  39. C = Matrix(x -1 ,y - 1) + 1
  40. End If
  41. A = Matrix(x - 1, y) + 1
  42. B = Matrix(x, y - 1) + 1
  43. If (A =< B and A =< C) Then Matrix(x, y) = A
  44. If (B =< C and B =< A) Then Matrix(x, y) = B
  45. If (C =< A and C =< B) Then Matrix(x, y) = C
  46. Next
  47. Next
  48. '计算 LD 值
  49. If (Len(str1) > Len(str2)) Then
  50. K = Len(str1)
  51. Else
  52. K = Len(str2)
  53. End If
  54. GetLevenshteinDistince = FormatNumber(1 - (Matrix(Len(str2), Len(str1)) / K), 3, True)
  55. End Function
复制代码

返回列表