Skip to content

Instantly share code, notes, and snippets.

@anandkunal
Created March 10, 2010 06:06
Show Gist options
  • Save anandkunal/327579 to your computer and use it in GitHub Desktop.
Save anandkunal/327579 to your computer and use it in GitHub Desktop.
import sets
import string
whitespace = sets.ImmutableSet(string.whitespace)
def qs(test_string, abbreviation, offset=None):
offset = offset or 0
if len(abbreviation) == 0: return 0.9
if len(abbreviation) > len(test_string): return 0.0
for i in xrange(len(abbreviation), 0, -1):
sub_abbreviation = abbreviation[0:i]
index = test_string.find(sub_abbreviation)
if index < 0: continue
if index+len(abbreviation) > len(test_string)+offset: continue
next_string = test_string[index+len(sub_abbreviation)::]
next_abbreviation = None
if (i >= len(abbreviation)): next_abbreviation = ''
else: next_abbreviation = abbreviation[i::]
remaining_score = qs(next_string, next_abbreviation, offset+index)
if remaining_score > 0:
score = len(test_string)-len(next_string)
if index != -1:
j, c = 0, test_string[index-1]
if c in whitespace:
for j in xrange(index-2, -1, -1):
c = test_string[j]
if c in whitespace: score = 1
else: score = 0.15
else:
score -= index
score += remaining_score*len(next_string)
score /= len(test_string)
return score
return 0.0
# Tests
print qs("hello world", "nothing is here")
print qs("hello world", "ow")
print qs("hello world", "helo")
print qs("hello world", "hello world")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment