Let's say I have the following lines:Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit.Phasellus congue nisi vel lorem dignissim tristique. (tag)Etiam vulputate lacus nec velit lobortis ut adipiscing mauris condimentum. (tag )Vestibulum quis nulla id nisi ultricies placerat. (teg)In tempus vulputate ante, quis suscipit nunc euismod in. (teg )Phasellus iaculis diam in felis pellentesque tristique. (ta g)(tag Praesent vestibulum sollicitudin velit, non mollis lacus scelerisque in.Nunc ac erat enim, at lobortis libero. (interesting)There's supposed to be a tag in each line enclosed in parenthesis.  But as you can see the data is very dirty and there's extra spaces inside tags, missing parents, misspelled tags, etc.How would I identify the lines containing (tag) or something similar?  The output I would expect in the example is to retrieve all lines, except for the last.I need to compare a long string to a shorter sub-string, so something like Levenshtein distance wont work (or will it?).  Tokenized techniques seem to rigid, because although I might tokenize everything in parenthesis, what happens when a parenthesis is missing?
Fuzzy search for a sub-string without tokens
algorithms;search
I will answer my own question with these links:http://codehost.wordpress.com/2011/09/13/fuzzy-substring-matching/http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/The second link contains the following function:def fuzzy_substring(needle, haystack):    Calculates the fuzzy match of needle in haystack,    using a modified version of the Levenshtein distance    algorithm.    The function is modified from the levenshtein function    in the bktree module by Adam Hupp    m, n = len(needle), len(haystack)    # base cases    if m == 1:        return not needle in haystack    if not n:        return m    row1 = [0] * (n+1)    for i in range(0,m):        row2 = [i+1]        for j in range(0,n):            cost = ( needle[i] != haystack[j] )            row2.append( min(row1[j+1]+1, # deletion                               row2[j]+1, #insertion                               row1[j]+cost) #substitution                           )        row1 = row2    return min(row1)lines = Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit.Phasellus congue nisi vel lorem dignissim tristique. (tag)Etiam vulputate lacus nec velit lobortis ut adipiscing mauris condimentum. (tag )Vestibulum quis nulla id nisi ultricies placerat. (teg)In tempus vulputate ante, quis suscipit nunc euismod in. (teg )Phasellus iaculis diam in felis pellentesque tristique. (ta g)(tag Praesent vestibulum sollicitudin velit, non mollis lacus scelerisque in.Nunc ac erat enim, at lobortis libero. (interesting).split('\n')for line in lines:    print fuzzy_substring('(tag)', line), lineThe output is:0 Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit.0 Phasellus congue nisi vel lorem dignissim tristique. (tag)1 Etiam vulputate lacus nec velit lobortis ut adipiscing mauris condimentum. (tag )1 Vestibulum quis nulla id nisi ultricies placerat. (teg)2 In tempus vulputate ante, quis suscipit nunc euismod in. (teg )1 Phasellus iaculis diam in felis pellentesque tristique. (ta g)1 (tag Praesent vestibulum sollicitudin velit, non mollis lacus scelerisque in.3 Nunc ac erat enim, at lobortis libero. (interesting)