String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack

Question

My use case is that I have a list of emails and I need to find if the email is in the chain:

emails = [
    ['    RE: I just got your test || This is a top level email roughly 300+ words in length on average'],
    ['RE:RE: Something | RE: Something | This is another entirely distinct email that is the top level'],
    ['RE: FooBar | A third email that is entirely distinct']
    ... #performance issues start occurring with emails growing to > 50 items
]

Now I would search for an email which is a reply:

test_email = """
A third email that is entirely distinct
"""

Currently I am using a KMP type search but I believe this is inefficient because it searches for multiple copies of the needle. I also believe the in operator is inefficient because it is using the niave method of searching the string.

An implementation of KMP in python I found and modified slightly:

class KMP:
    @classmethod
    def partial(self, pattern):
        """ Calculate partial match table: String -> [Int]"""
        ret = [0]

        for i in range(1, len(pattern)):
            j = ret[i - 1]
            while j > 0 and pattern[j] != pattern[i]:
                j = ret[j - 1]
            ret.append(j + 1 if pattern[j] == pattern[i] else j)
        return ret

    @classmethod  
    def search(self, T, P):
        """ 
        KMP search main algorithm: String -> String -> [Int] 
        Return all the matching position of pattern string P in S
        """
        partial, ret, j = KMP.partial(P), [], 0

        for i in range(len(T)):
            while j > 0 and T[i] != P[j]:
                j = partial[j - 1]
            try:
                if T[i] == P[j]: j += 1
            except:
                return False
            if j == len(P): 
                return True
        return False

Used here:

for choice in choices: #choice[0] is email in the reply chain
    if current_email == choice[0]:
        incident_type = choice[1]
        break
    elif len(current_email) > len(choice[0]):
        if KMP.search(current_email, choice[0]):
            incident_type = choice[1]
            break
    else:
        if KMP.search(choice[0], current_email):
            incident_type = choice[1]
            break

Should I fix this implementation or scrap it in favor of another algo?

Are you just searching Subject lines? And completely ignoring References/In-Reply-To, etc.? — Toby Speight
– Toby Speight, Commented Sep 12, 2018 at 14:34
@TobySpeight I am just searching the body of the email. The RE:s represent where there would be a RE in the body of the email. I am seeing if one body email is in another body email. The examples are shorter because I wanted a minimal example — Ryan Schaefer
– Ryan Schaefer, Commented Sep 12, 2018 at 14:35
Given the emails, are you capable of separating the bodies of each level? Is there a separator that always appears like your used | ? — juvian
– juvian, Commented Sep 12, 2018 at 14:49
@juvian No, the emails are real world corporate type emails. Again, the examples are not at all representative of the actual emails and are simplified for the sake of providing a minimal example. Also the actual emails I deal with cannot be disclosed. — Ryan Schaefer
– Ryan Schaefer, Commented Sep 12, 2018 at 14:55
Depending on how different your emails are, this could help: keep a frequency of each word that appears in your emails. Also keep for each word, the indexes of the emails in which it appears. Given the test_email, pick the 3 words that have the lowest frequency, intersect the indexes where those words appear, and then do the string search on those indexes (the in python operator should be good enough) — juvian
– juvian, Commented Sep 12, 2018 at 14:59

Gareth Rees · Accepted Answer · 2018-09-12 15:19:04Z

In the post you write:

I also believe the in operator is inefficient because it is using the naïve method of searching the string.

But if you look at the implementation of Python's in operator for strings, you find that it calls the FASTSEARCH function, which is "based on a mix between Boyer–Moore and Horspool".

The problem of searching many times for strings in a collection of documents is known as full-text search. The approach in the post is to search for the string in each document in turn: this scales linearly with the number and length of the documents. To improve on this scaling behaviour, you need to preprocess the collection of documents into an index. (Note that this only helps if you are searching many times—if you are searching only once, then you can't do better than searching each document.)

Here's a simple demonstration of the full-text search approach:

from collections import defaultdict

class SearchIndex:
    "A full-text search index."

    def __init__(self):
        # Mapping from word to set of documents containing that word.
        self._index = defaultdict(set) 

    def add(self, document):
        "Add document to the search index."
        for word in document.split():
            self._index[word].add(document)

    def search(self, query):
        "Generate the documents containing the query string."
        candidates = min((self._index[word] for word in query.split()), key=len)
        for document in candidates:
            if query in document:
                yield document

This works by building a mapping from words to the sets of documents containing each word (an "inverted index"). When a document is added to the index, it is split into words by calling str.split, and the document is added to the mapping for each word. This is conveniently implemented using collections.defaultdict.

To search for a string, the string is also split into words, and the index consulted for each word. The rarest word (the one mapping to the fewest number of documents) is used to get a set of candidates, and then each candidate is searched for the entire string.

This is a very simple approach and there are many refinements you can make. In particular, if you are going to be making queries of the same set of documents over a long period of time then you will want to make your inverted index persistent, and for that you will want a full-text search engine or database.

Is there a modification I can use to check just once for a match instead of all matching documents? (i.e. should I just return true if query in document) — Ryan Schaefer
– Ryan Schaefer, Commented Sep 12, 2018 at 15:26
@RyanSchaefer any(search_index.search(query) will return True if any of the documents contains query (and stop after the first is found). — Graipher
– Graipher, Commented Sep 12, 2018 at 15:28
If the only thing you need to know is whether there are any matches, then yes, replace yield document with return True (and add return False at the end). But surely at some point you will want to know about the actual documents found? — Gareth Rees
– Gareth Rees, Commented Sep 12, 2018 at 15:29

Stack Exchange Network

String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack

1 Answer 1

You must log in to answer this question.

Hot Network Questions

String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions