I am trying to write an algorithm that starts with a corpus of texts (e.g., a Wikipedia dump). It first builds an array of individual characters (e.g.,
" ") and frequent substrings (e.g,
" the ",
"some"). Then it splits up the text corpus into a sequence of those substrings.
I build the array as follows (not optimal but it's probably good enough):
from collections import defaultdict corpus = [ ] # An array of strings, each string being a text max_len = 5 # Longest sequence of characters to look for strings = defaultdict(int) for text in corpus: for n in range(max_len): for i in range(len(text)): if i+n < len(text): strings[text[i:i+n+1]] += 1 dict_size = 1000000 # Rough number of sequences to keep min_count = sorted(strings.values(), reverse=True)[dict_size] for key, count in strings.items(): if count < min_count and len(key) > 1: # Keep frequent sequences and all individual chars del strings[key]
The part that seems trickiest is doing a good (or optimal) split of the texts. I assumed that longer substrings are less frequent and shorter substrings are less likely to collide, so my idea was to take a greedy approach: I run through the text sequentially once for each possible length in decreasing order. I use a linked list to keep track of the split out text:
class Token: def __init__(self, text, next=None): self._text = text self._next = next self._done = False @property def next(self): return self._next @next.setter def next(self, token): self._next = token @property def text(self): return self._text @text.setter def text(self, text): self._text = text @property def done(self): return self._done @done.setter def done(self, status): self._done = status for text in corpus: head = Token(text) # Start the list with one token of the whole text for n in range(max_len, 0, -1): # Run through lengths in decreasing order token = head # Go back to the start for each run i = 0 while True: if token.done or i+n > len(token.text): # If token is processed or end of token is reached if token.next: token = token.next # Continue linked list i = 0 continue else: break if token.text[i:i+n] in strings: if i > 0: # Split out characters before match token.next = Token(token.text[i:], token.next) token.text = token.text[:i] token = token.next token.done = True if len(token.text) > n: # Split out characters after match token.next = Token(token.text[n:], token.next) token.text = token.text[:n] token = token.next i = 0 else: i += 1 # Run through characters in the token
This seems to work but I'm not sure how optimal it actually is, and I can't think of an algorithm that wouldn't run in exponential time. Initially I thought this may be a dynamic programming question but I don't think it works either because the character space is so sparse.