VB.NET - 다른 목록에 대한 큰 일반 목록 필터링

Question

두 개의 일반 문자열 목록이 있습니다. 첫 번째 문자열에는 약 1,000,000 개의 용어가 포함되고 두 번째 문자열에는 약 100,000 개의 키워드가 포함됩니다. 첫 번째 목록의 용어는 두 번째 목록의 키워드를 포함 할 수도 있고 포함하지 않을 수도 있습니다. 첫 번째 목록에서 두 번째 목록의 키워드를 포함하지 않는 용어를 분리해야합니다. 는 현재 내가 (프레임 워크 3.5과 VB.NET)이 같은 일을 해요 :

For Each keyword In keywordList 
    termList.RemoveAll(AddressOf ContainsKeyword) 
Next 

Private Shared Function ContainsKeyword(ByVal X As String) As Integer 
    If X.IndexOf(keyword) >= 0 Then 
     Return True 
    Else 
     Return False 
    End If 
End Function 

말할 필요도없이,이 영원히합니다. 가장 빠른 방법은 무엇입니까? 아마도 사전을 사용하고 있을까요? 어떤 힌트라도 도움이 될 것입니다

Answer 1

똑바로 동등한 검사가 아닌 Contains 검사를 수행하기 때문에 키워드의 곧은 사전이 작동하지 않습니다. 취할 수있는 한 가지 접근 방법은 검색 용어를 하나의 트리로 결합하는 것입니다. 트리가 도움이되는 양은 검색 용어에 얼마나 많은 중복이 있는지에 달려 있습니다. 나는 출발점으로 (많은 테스트없이) 기본 트리 구현을 함께 넣어 :

Public Class WordSearchTree 

    Private ReadOnly _branches As New Dictionary(Of Char, WordSearchTree) 

    Public Function WordContainsTerm(ByVal word As String) As Boolean 
     Return Not String.IsNullOrEmpty(word) AndAlso _ 
       Enumerable.Range(0, word.Length - 1) _ 
         .Any(Function(i) WordContainsInternal(word, i)) 
    End Function 

    Private Function WordContainsInternal(ByVal word As String, ByVal charIndex As Integer) As Boolean 
     Return _branches.Count = 0 OrElse _ 
       (_branches.ContainsKey(word(charIndex)) AndAlso _ 
       charIndex < word.Length - 1 AndAlso _ 
       _branches(word(charIndex)).WordContainsInternal(word, charIndex + 1)) 
    End Function 

    Public Shared Function BuildTree(ByVal words As IEnumerable(Of String)) As WordSearchTree 
     If words Is Nothing Then Throw New ArgumentNullException("words") 
     Dim ret As New WordSearchTree() 
     For Each w In words 
      Dim curTree As WordSearchTree = ret 
      For Each c In w 
       If Not curTree._branches.ContainsKey(c) Then 
        curTree._branches.Add(c, New WordSearchTree()) 
       End If 
       curTree = curTree._branches(c) 
      Next 
     Next 
     Return ret 
    End Function 

End Class 

그 나무와 함께, 당신은 다음과 같이 할 수 있습니다 : 당신은 그냥 있다면, 하나를 들어

Dim keys As WordSearchTree = WordSearchTree.Build(keywordList) 
termList.RemoveAll(AddressOf keys.WordContainsTerm)