# Optimally splitting a text into strings from a set

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., "a", "b", "7", "0", ".", " ") and frequent substrings (e.g, " the ", "ly ", " un", "er", "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.

• What about: from collections import Counter Is there any reason why you dont use it? Just asking. I have hard times understand what you are trying to achieve. What about some sample of input and desired output? – Pavel Hanpari Aug 17 '17 at 17:11
• This is a preprocessing step in a natural language processing learning task. The first piece of code is trying to find frequent combinations of characters. The second piece would try to split the texts in the corpus in as few chunks as possible (e.g., I'm splitting the word "amazingly" and my dictionary has individual characters and "maz", "amaz", "ing" and "ly"; ["amaz", "ing", "ly"] would be a better split than ["a", "maz", "ing", "ly"] or ["a", "m", "a", "z", "ing", "ly"]) – wizplum Aug 17 '17 at 19:24