Skip to content

Instantly share code, notes, and snippets.

@chuanconggao
Last active January 22, 2024 06:00
Show Gist options
  • Save chuanconggao/4df9c1b06fa7f3ed854d5d96e2ae499f to your computer and use it in GitHub Desktop.
Save chuanconggao/4df9c1b06fa7f3ed854d5d96e2ae499f to your computer and use it in GitHub Desktop.
The original minimal 15 lines implementation of PrefixSpan. Full library at https://github.com/chuanconggao/PrefixSpan-py.
from collections import defaultdict
def frequent_rec(patt, mdb):
results.append((len(mdb), patt))
occurs = defaultdict(list)
for (i, startpos) in mdb:
seq = db[i]
for j in range(startpos + 1, len(seq)):
l = occurs[seq[j]]
if len(l) == 0 or l[-1][0] != i:
l.append((i, j))
for (c, newmdb) in occurs.items():
if len(newmdb) >= minsup:
frequent_rec(patt + [c], newmdb)
db = [
[0, 1, 2, 3, 4],
[1, 1, 1, 3, 4],
[2, 1, 2, 2, 0],
[1, 1, 1, 2, 2],
]
minsup = 2
results = []
frequent_rec([], [(i, -1) for i in range(len(db))])
print(results)
@Sandy4321
Copy link

cool

@shas043
Copy link

shas043 commented Nov 17, 2022

Hi, can you suggest how to get the above results for large datasets (100-500 values in each list)?

@TensorBlast
Copy link

Hi Could you please name the variables so they match with the Prefix Span algorithm naming scheme? Also would appreciate if you could explain the intuition behind the lines of code using comments.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment