Examples

Using a set index:

import setix

ix = setix.SetIntersectionIndex ()
ix.add ((1, 2, 3))
ix.add ((1, 2, 4))
ix.add ((2, 3, 4))

ix.find ((1, 2), 1).get_list()
# returns [(2, [(1, 2, 3)]),
#          (2, [(1, 2, 4)]),
#          (1, [(2, 3, 4)])]
# (the order of the first two results can change as they have equal scores)

Using a trigram index:

import setix.trgm

ix = setix.trgm.TrigramIndex ()
ix.add ("strength")
ix.add ("strenght")
ix.add ("strength and honor")

ix.find ("stremgth", threshold=1).get_list()
# returns [(6, ["strength and honor"])
#          (6, ["strength"]),
#          (4, ["strenght"])]

ix.find_similar ("stremgth", threshold=0.1).get_list()
# returns [(0.5,  ["strength"]),           # 6 intersections / (9 total + 9 total - 6)
#          (0.29, ["strenght"]),           # 4 intersections / (9 total + 9 total - 4)
#          (0.27, ["strength and honor"])] # 6 intersections / (9 total + 19 total - 6)

In general, to search for phrases containing a misspelt word, a threshold of -3*N can be given where N is the number of misspellings.

ix.find ("stremgth", threshold=-3).get_list()
# returns [(6, ["strength and honor"]),
#          (6, ["strength"])]

Benchmarks

A benchmark is included in tests/dvd_db_test.py

Results from an Athlon II running at 2.6GHz:

In [1]: import tests.dvd_db_test
Loading database...
Extracted 240577 titles
Memory used by data: 107.8MB
Building index...
CPU time used: 43.1s
Unique trigrams indexed: 11352
Unique phrases indexed: 228620
Memory used by index: 80.9MB

In [2]: %timeit list (tests.dvd_db_test.titles.find("daft punk", 8))
10 loops, best of 3: 27.8 ms per loop

In [3]: %timeit list (tests.dvd_db_test.titles.find("daft punk", 1))
10 loops, best of 3: 86.4 ms per loop

In [1]: import tests.dvd_db_test
Loading database...
Extracted 240577 titles
Memory used by data: 108.8MB
Building index...
CPU time used: 45.8s
Unique trigrams indexed: 11352
Unique phrases indexed: 228620
Memory used by index: 86.2MB

In [2]: %timeit list (tests.dvd_db_test.titles.find("daft punk", 8))
10 loops, best of 3: 27.9 ms per loop

In [3]: %timeit list (tests.dvd_db_test.titles.find("daft punk", 1))
10 loops, best of 3: 86.3 ms per loop