Fuzzy search

fuzzy_search.py

'''
 Fuzzy search algorithm inspired by sublimetext.
'''

with open('/usr/share/dict/words') as f:
    words = f.read().split('\n')

def fuzzy_match (q):
    ''' Match a query string q against a candidate string s, where len(q) <= len(s).
    Returns true iff q is an ordered subset of s, or false otherwise.
    ('sbl' is an ordered subset of 'sublime'; 'stbl' and 'slb' are not)
    '''
    def match (s):
        i, j = len(s), len(q)
        while j != 0 and i >= j:
            if s[i-1] == q[j-1]:
                j -= 1
            i -= 1
        return j == 0
    return match

def matching_words (q):
    return filter(fuzzy_match(q), words)

queries = [ 'abaion', 'cmkng', 'sblme' ]

for q in queries:
    print('%s: %s'%(q, '\n\t'.join(
        sorted(matching_words(q),key=len))))

output.txt

abaion: abaction
    ablation
    abrasion
    jawbation
    abaptiston
    abdication
    aberration
    abjuration
    abnegation
    abreaction
    abrogation
    accubation
    albication
    ambulation
    dealbation
    habitation
    pabulation
    tabulation
    trabeation
    zabaglione
    abacination
    ablactation
    abomination
    absentation
    abstraction
    adumbration
    approbation
    arbitration
    calibration
    carbonation
    carburation
    elaboration
    fabrication
    habituation
    labefaction
    saburration
    stabulation
    syllabation
    tabefaction
    abalienation
    abbreviation
    aberrational
    abevacuation
    abirritation
    abjudication
    adverbiation
    albification
    albitization
    anaerobation
    antiabrasion
    arborization
    assibilation
    cohabitation
    deambulation
    exacerbation
    flabellation
    habilitation
    habitational
    inhabitation
    labilization
    masturbation
    obambulation
    palpebration
    vocabulation
    abstractional
    accombination
    ambagiousness
    antilibration
    arbitrational
    barbarization
    carbonatation
    carbonization
    carboxylation
    carburization
    collaboration
    confabulation
    decarburation
    diabolization
    funambulation
    labefactation
    labialization
    marbleization
    nonabdication
    nonabjuration
    perambulation
    preambulation
    pretabulation
    reapprobation
    rearbitration
    recalibration
    recarbonation
    Sabbatization
    stabilization
    syllabication
    trabeculation
    unapprobation
    abarticulation
    absolutization
    abstractionism
    abstractionist
    albumenization
    albuminization
    algebraization
    ambicoloration
    anteambulation
    arbitrationist
    barbariousness
    disapprobation
    Jacobinization
    malobservation
    malpublication
    masturbational
    noctambulation
    nonabsentation
    parabolization
    preapprobation
    prefabrication
    proarbitration
    recohabitation
    rehabilitation
    reinhabitation
    somnambulation
    subapprobation
    tabularization
    transverbation
    alphabetization
    anticombination
    archabomination
    cannibalization
    carbonatization
    carbonification
    debarbarization
    decarbonization
    decarboxylation
    decarburization
    delabialization
    diabolification
    dishabilitation
    habilimentation
    interarboration
    interhabitation
    overelaboration
    parabaptization
    preinhabitation
    rebarbarization
    recarbonization
    recarburization
    syllabification
    circumambulation
    collaborationism
    collaborationist
    flabbergastation
    malleabilization
    missyllabication
    noncollaboration
    superabomination
    tintinnabulation
    transverberation
    autohybridization
    decarboxylization
    nonrehabilitation
    proarbitrationist
    resyllabification
    disprobabilization
    dissyllabification
    impermeabilization
    supercarbonization
    transubstantiation
    protransubstantiation
    transubstantiationite
    transubstantiationalist
cmkng: canmaking
    capmaking
    cupmaking
    cakemaking
    cardmaking
    cartmaking
    casemaking
    clogmaking
    coinmaking
    combmaking
    conemaking
    coremaking
    corkmaking
    facemaking
    lacemaking
    lockmaking
    pacemaking
    packmaking
    sackmaking
    sockmaking
    blockmaking
    brickmaking
    candymaking
    chainmaking
    chairmaking
    cloakmaking
    clockmaking
    clothmaking
    coachmaking
    colormaking
    couchmaking
    cratemaking
    creammaking
    matchmaking
    peacemaking
    placemaking
    saucemaking
    stockmaking
    trucemaking
    watchmaking
    bodicemaking
    bucketmaking
    candlemaking
    carpetmaking
    cementmaking
    coffinmaking
    cradlemaking
    speechmaking
    starchmaking
    biscuitmaking
    cabinetmaking
    picturemaking
    stencilmaking
    trenchermaking
    spectaclemaking
sblme: sublime
    sublimed
    sublimer
    resublime
    sublimate
    sublimely
    sublimize
    subalmoner
    subclimate
    subelement
    sublimable
    subpalmate
    unsublimed
    disablement
    oversublime
    sublimeness
    subultimate
    scramblement
    scribblement
    stablishment
    unsublimable
    unsublimated
    disenablement
    establishment
    subelementary
    subglumaceous
    substalagmite
    disbalancement
    disembowelment
    sublimableness
    coestablishment
    supersublimated
    unestablishment
    disestablishment
    establishmentism
    spectrobolometer
    spectrobolometric
    establishmentarian
    superestablishment
    nondisestablishment
    counterestablishment
    disestablishmentarian
    establishmentarianism
[Finished in 1.6s]