Levenshtein distanz

    • VB.NET

    Es gibt 6 Antworten in diesem Thema. Der letzte Beitrag () ist von picoflop.

      Levenshtein distanz

      Berechnet das Maß der Ähnlichkeit zweier Strings.
      Mehr Infos zu Levenshtein (nicht: Levenstein) bietet ... Wikipedia ;)

      Funktion:
      Spoiler anzeigen

      VB.NET-Quellcode

      1. ''' <summary>
      2. ''' Berechnet die Levenshtein Distanz zweier Strings.
      3. ''' Dies ist quasi ein Maß der Ähnlichkeit
      4. ''' </summary>
      5. ''' <param name="s">String 1</param>
      6. ''' <param name="t">String 2</param>
      7. ''' <returns>Levenshtein Distanz</returns>
      8. ''' <remarks>C# Sample nach VB portiert
      9. ''' Original: http://www.merriampark.com/ldcsharp.htm
      10. ''' </remarks>
      11. Public Function Levenshtein(ByVal s As String, ByVal t As String) As Integer
      13. Dim n As Integer = s.Length
      14. Dim m As Integer = t.Length
      15. Dim d(n + 1, m + 1) As Integer ' matrix
      16. Dim cost As Integer
      18. ' Step 1
      20. If n = 0 Then Return m
      21. If m = 0 Then Return n
      23. ' Step 2
      25. For i As Integer = 0 To n
      26. d(i, 0) = i
      27. Next
      28. For j As Integer = 0 To m
      29. d(0, j) = j
      30. Next
      32. ' Step 3
      33. For i = 1 To n
      34. For j = 1 To m
      35. ' Kosten für eine Position:
      36. If t(j - 1) = s(i - 1) Then
      37. cost = 0
      38. Else
      39. cost = 1
      40. End If
      41. d(i, j) = System.Math.Min(System.Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost)
      43. Next j
      44. Next i
      46. Return d(n, m)
      48. End Function



      Nachtrach:
      Hab mal ein bißchen rumgebastelt und das ganze in ne Klasse gepackt und ne Testfunktion geschrieben. Außerdem hab ich mal Multithreading implementiert.

      Klasse:
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Imports System.IO
      2. Imports System.Threading
      4. Public Class Levenshtein
      6. Private Structure ThreadArgs
      7. Dim SearchString As String
      8. Dim SrcArray() As String
      9. Dim startIndex As Integer
      10. Dim endInex As Integer
      11. Dim DstList As List(Of String)
      12. Dim MaxDistanz As Integer
      13. Dim ARE As AutoResetEvent
      14. End Structure
      16. Private Shared WordList() As String
      18. Public Shared Sub DoubleList()
      20. Dim tmp(WordList.Length * 2 - 1) As String
      21. For i = 0 To tmp.Length - 1
      22. tmp(i) = WordList(i Mod WordList.Length)
      23. Next
      24. WordList = tmp
      27. End Sub
      29. Public Shared Function GetWordList(ByVal fname As String) As Integer
      31. Try
      32. WordList = IO.File.ReadAllLines(fname)
      33. Return WordList.Count
      34. Catch ex As Exception
      35. Return -1
      36. End Try
      38. End Function
      40. Public Shared Function GetThreadedLevenshteinList(ByVal s As String, ByVal MaxDistanz As Integer, ByVal NumThreads As Integer) As List(Of String)
      42. Dim l(NumThreads - 1) As List(Of String)
      43. Dim are(NumThreads - 1) As AutoResetEvent
      44. Dim tos(NumThreads - 1) As ThreadArgs
      46. Dim startindex As Integer = 0, numwords As Integer = WordList.Count \ NumThreads
      47. For i As Integer = 0 To NumThreads - 1
      48. l(i) = New List(Of String)
      49. are(i) = New AutoResetEvent(True)
      50. With tos(i)
      51. .SearchString = s
      52. .SrcArray = WordList
      53. .startIndex = startindex
      54. .endInex = Math.Min(.startIndex + numwords - 1, WordList.Length - 1)
      55. startindex += numwords
      56. .MaxDistanz = MaxDistanz
      57. .DstList = l(i)
      58. .ARE = are(i)
      59. .ARE.Reset()
      60. End With
      61. Dim t As New Thread(AddressOf GetLevenshteinListThread)
      62. t.Start(tos(i))
      63. Next
      65. System.Threading.WaitHandle.WaitAll(are)
      67. GetThreadedLevenshteinList = New List(Of String)
      68. For i As Integer = 0 To NumThreads - 1
      69. For Each st As String In tos(i).DstList
      70. GetThreadedLevenshteinList.Add(st)
      71. Next
      72. Next
      74. Return GetThreadedLevenshteinList
      76. End Function
      78. Private Shared Sub GetLevenshteinListThread(ByVal o As Object)
      80. Dim tos As ThreadArgs = DirectCast(o, ThreadArgs)
      82. Dim crntl As Integer
      83. Dim wort As String = String.Empty
      85. For i As Integer = tos.startIndex To tos.endInex
      86. crntl = Distanz(tos.SearchString, tos.SrcArray(i))
      87. If crntl < tos.MaxDistanz Then
      88. tos.DstList.Add(tos.SrcArray(i))
      89. End If
      90. Next
      92. tos.ARE.Set()
      94. End Sub
      96. Public Shared Function GetLevenshteinList(ByVal s As String, ByVal MaxDistanz As Integer) As List(Of String)
      98. Dim crntl As Integer
      99. Dim wort As String = String.Empty
      101. Dim l As New List(Of String)
      103. For Each t As String In WordList
      104. crntl = Distanz(s, t)
      105. If crntl < MaxDistanz Then
      106. l.Add(t)
      107. End If
      108. Next
      110. Return l
      112. End Function
      115. ''' <summary>
      116. ''' Berechnet die Levenshtein Distanz zweier Strings.
      117. ''' Dies ist quasi ein Maß der Ähnlichkeit
      118. ''' </summary>
      119. ''' <param name="s">String 1</param>
      120. ''' <param name="t">String 2</param>
      121. ''' <returns>Levenshtein Distanz</returns>
      122. ''' <remarks>C# Sample nach VB portiert
      123. ''' Original: http://www.merriampark.com/ldcsharp.htm
      124. ''' </remarks>
      125. Public Shared Function Distanz(ByVal s As String, ByVal t As String) As Integer
      127. Dim n As Integer = s.Length
      128. Dim m As Integer = t.Length
      129. Dim d(n + 1, m + 1) As Integer ' matrix
      130. Dim cost As Integer
      132. ' Step 1
      134. If n = 0 Then Return m
      135. If m = 0 Then Return n
      137. ' Step 2
      139. For i As Integer = 0 To n
      140. d(i, 0) = i
      141. Next
      142. For j As Integer = 0 To m
      143. d(0, j) = j
      144. Next
      146. ' Step 3
      147. For i = 1 To n
      148. For j = 1 To m
      149. ' Kosten für eine Position:
      150. If t(j - 1) = s(i - 1) Then
      151. cost = 0
      152. Else
      153. cost = 1
      154. End If
      155. d(i, j) = System.Math.Min(System.Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost)
      157. Next j
      158. Next i
      160. Return d(n, m)
      162. End Function
      164. End Class


      Testform:
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Option Strict On
      3. Imports System.ComponentModel
      4. Imports System.IO
      6. Public Class Form1
      8. Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
      10. ' wortliste von: wortschatz.uni-leipzig.de/Papers/top10000de.txt
      11. Levenshtein.GetWordList(Path.Combine(My.Computer.FileSystem.SpecialDirectories.MyDocuments, "top10000de.txt"))
      12. ' liste auf 320.000 aufpusten
      13. For i As Integer = 1 To 5
      14. Levenshtein.DoubleList()
      15. Next
      17. End Sub
      19. Private Delegate Sub dlgSetListbox(ByVal s As String)
      20. Private Sub SetListbox(ByVal s As String)
      21. ListBox1.Items.Add(s)
      22. End Sub
      24. Private Sub RunInOtherThread()
      26. Dim stp As New Stopwatch
      27. Dim l As List(Of String)
      29. stp.Start()
      30. l = Levenshtein.GetThreadedLevenshteinList("Haus", 2, 2)
      31. Dim ms As Long = stp.ElapsedMilliseconds
      33. Dim d As dlgSetListbox = AddressOf SetListbox
      34. ListBox1.Invoke(d, "Threaded: " & ms.ToString)
      36. End Sub
      39. Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
      41. ' Leider können wir die threaded funktion nicht aus dem Hauptthread aufrufen,
      42. ' weil der STAThread ist und dann geht WaitHandle.WaitAll nicht
      43. ' Also schmeissen wir mal nen dummy thread an ;)
      44. Dim t As New Threading.Thread(AddressOf RunInOtherThread)
      45. t.Start()
      47. End Sub
      49. Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
      51. Dim stp As New Stopwatch
      52. Dim l As List(Of String)
      54. stp.Start()
      55. l = Levenshtein.GetLevenshteinList("Haus", 2)
      56. Dim ms As Long = stp.ElapsedMilliseconds
      57. ListBox1.Items.Add("Single: " & ms.ToString)
      59. End Sub
      60. End Class


      Die singlethreaded Methode braucht bei mir (dual-core) im schnitt 1050 ms, die Multithread Methode im Schnitt 700 ms.

      Wenn jemand das ganze evtl mal auf nem i920 mit aktiviertem HT ausprobieren könnte ... ;)
      (PS: Anzahl der threads dann natürlich auf 4 oder 8 setzen!)

      Wortliste runterladen nicht vergessen!

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „picoflop“ ()

      picoflop schrieb:

      Wenn jemand das ganze evtl mal auf nem i920 mit aktiviertem HT ausprobieren könnte ...

      So ganz scherzhaft war das nicht gemeint.
      Wenn jemand das mal auf nem "normalen" Quad (mit 4 Threads) bzw nem Quad+HT laufen lassen könnte und ggfs dann mal die Zeiten postet, fänd' ich das schon ganz interessant.

      push ... ;)

      Hab's jetzt mal einen "normalen" Aufruf (Vergleich zweier worte) ausgestoppt (mit dem HiPerfTimer):

      VB.NET-Quellcode

      1. For i = 1 To 1000
      2. Levenshtein.Distanz("Bahnhofsvorplatzgestaltungsideenwettbewerb", "Raketenabschussrampenreinigungspersonal")
      3. Next

      Braucht auf meinem kröppeligen Turion 1.6 GHz gerade mal rund 0.2 Sekunden. Ein einzelner Aufruf braucht rund 0.2 - 0.3 Millisekunden.

      Boolean schrieb:

      Zeitspanne für 100.000 messbar sein wird..

      1. sind es 320.000 Worte ... ;)
      2. evtl mal den HiPerfTimer (SuFu forum) zum messen nehmen. Der hat ne kleinere Auflösung. Im Zweifel kann man natürlich auch noch me 1-10 Schleife umzu bauen.

      3. Interessant wäre es schon. Insb. mal Werte für 1, 2, 4 und 8 Threads.

    Facebook
    Telefonspende