4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Pavel Hanpari Aug 17 '17 at 17:11
  • 2
    \$\begingroup\$ 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"]) \$\endgroup\$ – wizplum Aug 17 '17 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.