0
$\begingroup$

I'm supposed to write a (short) program that recognizes whether a given sample of text (10-200 words) comes from "Uncle Tom's Cabin," "Moby Dick," or "The Scarlet Letter". I cannot access the source texts at computation time. What are some approaches I can use?

$\endgroup$
  • $\begingroup$ Hi @Moronic, what have you tried? $\endgroup$ – Yamar69 Oct 21 at 11:20
  • $\begingroup$ I don't know anything about the topic, what should I try? $\endgroup$ – Moronic Oct 21 at 13:31
  • $\begingroup$ The requirement to"having no access to source text at computation time" is vague. Obviously you need some form of (possibly lossy) data from the text. What is valid? Word count? Word-pair count? A neutral network trained on text? First half of the text capitalised? $\endgroup$ – Apiwat Chantawibul Oct 22 at 0:41
0
$\begingroup$

You could try an approach inspired by a bloom filter. You make a counter for the distinct words in each text.

Then you save this somewhere and and check at computation time, if the all the words in the input appear at least as often in the full text as in the query:

  • If yes: The excerpt could be from that book
  • If no: The excerpt is not from that book

You can then improve on this in a few ways:

  1. Remove words that occur a lot in all input text from the query and from the counter (e.g. the occurrences of the in the query is likely not a good indicator for which book it is)
  2. If you need to use less storage, you could try to map the words to some range that has significantly less values as the number of input words. You could e.g. calculate the hash and only look at the first byte or only take the first 3 chars of a word
  3. You could do (2) but count occurrences using 2 (or more) distinct mappings (e.g. to first byte of MD5 and first byte of SHA1). This should reduce false positives with only a small increase in storage.
  4. You could count occurrences of groups of n words instead of single words. Depending on how you process the input, you have to apply different windowing techniques to your query.

Here a very simple implementation to get you started:

from collections import Counter

books = {
    "moby_dick": "i hate whales I have to slaughter all of them screw the white whale i am ahab ahoy mateys",
    "scarlet_letter": "i like to write letters a lot but my most favourite pasttime is writing letters on red paper preferably scarlet red",
    "uncle_toms_cabin": "on the weekend joe often went to a little shed in the woods to play with his dolls this shed was referred to as uncle toms cabin because it belonged to his uncle tom",
}


def preprocess(book):
    mappings = dict()
    for book,content in books.items():
        mappings[book] = Counter(content.lower().split())
    return mappings


def query(q, counters):
    words = Counter(q.lower().split())
    for book, word_counts in counters.items():
        possible = True
        for word, count_in_query in words.items():
            if word_counts[word] < count_in_query:
                possible = False
                break
        if possible:
            yield str(book)


def main():
    counters = preprocess(books)
    while True:
        q = input("Enter query: ")
        possible_books = query(q,counters)
        print(f"Could be either one of: " + " ,".join(possible_books))

if __name__ == "__main__":
    main()

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.