Return an iterable as a subset of a sequence of ngrams using the hailstorm algorithm. If `with_pos` is True also include the starting position for the ngram in the original sequence. Definition from the paper: http://www2009.eprints.org/7/1/p61.pdf The algorithm first finger
(ngrams, with_pos=False)
| 414 | |
| 415 | |
| 416 | def select_ngrams(ngrams, with_pos=False): |
| 417 | """ |
| 418 | Return an iterable as a subset of a sequence of ngrams using the hailstorm |
| 419 | algorithm. If `with_pos` is True also include the starting position for the |
| 420 | ngram in the original sequence. |
| 421 | |
| 422 | Definition from the paper: http://www2009.eprints.org/7/1/p61.pdf |
| 423 | |
| 424 | The algorithm first fingerprints every token and then selects a shingle s |
| 425 | if the minimum fingerprint value of all k tokens in s occurs at the first |
| 426 | or the last position of s (and potentially also in between). Due to the |
| 427 | probabilistic properties of Rabin fingerprints the probability that a |
| 428 | shingle is chosen is 2/k if all tokens in the shingle are different. |
| 429 | |
| 430 | For example: |
| 431 | >>> list(select_ngrams([(2, 1, 3), (1, 1, 3), (5, 1, 3), (2, 6, 1), (7, 3, 4)])) |
| 432 | [(2, 1, 3), (1, 1, 3), (5, 1, 3), (2, 6, 1), (7, 3, 4)] |
| 433 | |
| 434 | Positions can also be included. In this case, tuple of (pos, ngram) are returned: |
| 435 | >>> list(select_ngrams([(2, 1, 3), (1, 1, 3), (5, 1, 3), (2, 6, 1), (7, 3, 4)], with_pos=True)) |
| 436 | [(0, (2, 1, 3)), (1, (1, 1, 3)), (2, (5, 1, 3)), (3, (2, 6, 1)), (4, (7, 3, 4))] |
| 437 | |
| 438 | This works also from a generator: |
| 439 | >>> list(select_ngrams(x for x in [(2, 1, 3), (1, 1, 3), (5, 1, 3), (2, 6, 1), (7, 3, 4)])) |
| 440 | [(2, 1, 3), (1, 1, 3), (5, 1, 3), (2, 6, 1), (7, 3, 4)] |
| 441 | """ |
| 442 | ngram = None |
| 443 | last = None |
| 444 | for pos, ngram in enumerate(ngrams): |
| 445 | # FIXME: use a proper hash |
| 446 | nghs = [] |
| 447 | for ng in ngram: |
| 448 | if isinstance(ng, str): |
| 449 | ng = bytearray(ng, encoding='utf-8') |
| 450 | else: |
| 451 | ng = bytearray(str(ng).encode('utf-8')) |
| 452 | nghs.append(crc32(ng) & 0xffffffff) |
| 453 | min_hash = min(nghs) |
| 454 | if with_pos: |
| 455 | ngram = (pos, ngram,) |
| 456 | if min_hash in (nghs[0], nghs[-1]): |
| 457 | yield ngram |
| 458 | last = ngram |
| 459 | else: |
| 460 | # always yield the first or last ngram too. |
| 461 | if pos == 0: |
| 462 | yield ngram |
| 463 | last = ngram |
| 464 | if last != ngram: |
| 465 | yield ngram |