I want to share our fresh work — the BloomSpan algorithm for finding the longest frequent sequences of words in an array of texts. I named it BloomSpan.
What is it, in human terms. Imagine you have a library of 50,000 books, and you need to find all the long phrases that are repeated word for word, without omissions, in many different books. Not “similar” phrases, but exactly identical chains of words, and as long as possible — such that if you add another word to the left or right, the phrase no longer occurs frequently enough. The task sounds simple, but with billions of words, it stumbles on memory and time. Classic algorithms either build huge indexes or go through too many candidates.
Where is it needed? For example, extracting patterns from documents (such as uniform “headers” in letters or contracts), searching for borrowings and plagiarism, highlighting stable phrases and clichés in large text arrays.
So, here’s what we got. The algorithm. Honestly, BloomSpan is not exactly an algorithm from scratch but a careful assembly of known ideas which, when combined, have a strong effect. At its core – different ideas from BIDE+, FHK, and on top of that: (a) The Bloom filter — a compact structure that answers the question “has this combination of words occurred frequently enough?”, without storing the combinations themselves. It can occasionally make a mistake in the direction of “yes”, but never in the direction of “no”, ensuring we never miss a phrase we need (b) “Depth-first” search directly through the text — we find a short frequent core and gradually expand it into a long phrase, without creating intermediate copies of the corpus. (c) An occupancy map — marking positions in the text already “covered” by found phrases, to avoid checking the same thing many times.
The results. On the Gutenberg Project corpus of 50,000 books (about 3 billion words), BloomSpan operates 11-15 times faster than the classic FHK algorithm and consumes up to twice as little memory. It is the only tested method that manages to complete the entire corpus within 40 GB. Moreover, where they do finish, the results fully match those of the precise algorithms — meaning the speedup does not compromise quality.
On synthetic data with an “unnatural” distribution of words, good old FHK is faster. BloomSpan is specifically tailored for living natural language, and the article discusses why this is so.
The preprint and code (Java) — in the comments
