4 ms·

I've had a thought and am curious how people would solve it. Sometimes, if you copy words off a PDF lecture slide, all the words are mashed together (eg. Hello

I've had a thought and am curious how people would solve it. Sometimes, if you copy words off a PDF lecture slide, all the words are mashed together (eg. Hello Foo bar → HelloFoobar). Is this an AI domain or can it solved by simple programming?

eutectic 5y ago
I would try an n-gram model with dynamic programming. e.g. logp(_, "") = 0 logp(word0, text) = max(logp_bigram(word0, word1) + logp(word1, rest) for word1, rest in prefix_words(text))
gattilorenz 5y ago
"AI" and "simple programming" are not mutually exclusive :) look at the Speech and Language processing book, particularly chapter 3 about language models https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/ You can implement a language model based on character n-grams to calculate whether a sequence is more likely with or without a space. Of course you would need a way of estimating the proability of each sequence, which means you need a corpus to train your language model on.
wodenokoto 5y ago
This is a common problem in Japanese NLP, and while state of the art is using deep learning, almost everyone use dynamic programming or conditional random fields together with a dictionary to solve it. There also exists research on solving this problem unsupervised which basically invents new word boundaries for a language (remember that spoken languages doesn’t have word boundaries - it was invented for writing and strictly speaking, current spelling isn’t the only way to solve word boundaries for a given language)
tester34 5y ago
Have you tried using an ~~XML~~ PDF parser instead? /s and tried to find which sentence without spaces matches your sentence
ghusbands 5y ago
It's worth noting that different PDF-to-text tools (and different PDF-display tools that have text-copying) get different results and it can be worth trying a few. For the most part, the vector parts of a PDF and the association with the text is sufficient to discover spacing information.
deleted 5y ago
[deleted]
epilys 5y ago
It's called word segmentation. There are libraries for it: https://github.com/grantjenks/python-wordsegment https://github.com/grantjenks/python-wordsegment https://github.com/InstantDomain/instant-segment https://github.com/InstantDomain/instant-segment (rust) I used the latter to process pdf plain text output quite successfully.
eutectic 5y ago
I got nerd-sniped and wrote a simple Python solver for this problem. You can find the ngram files at Norvig's site (https://norvig.com/ngrams/ https://norvig.com/ngrams/). import collections import math import heapq with open('count_1w.txt', 'r') as f: unigrams = [l.split() for l in f] unigram_map = collections.defaultdict(lambda: 0) for word, count in unigrams: unigram_map[word] = int(count) with open('count_2w.txt', 'r') as f: bigrams = [l.split() for l in f] bigram_map = collections.defaultdict(lambda: collections.defaultdict(lambda: {})) for word0, word1, count in bigrams: bigram_map[word0][word1] = int(count) log_p_unseen = collections.defaultdict(lambda: 0.) for word0, counts in bigram_map.items(): for word1, count in counts.items(): unigram_map[word1] += count total = sum(counts.values()) #smoothing for unseen words mn, mx = min(counts.values()), max(counts.values()) if mn == mx: p_unseen = 0.5 else: #geometric series approximation r = (mn / mx) ** (1. / (len(counts) - 1)) n = mn * r / (1. - r) p_unseen = n / (n + total) log_p_unseen[word0] = math.log(p_unseen) c = (1. - p_unseen) / total bigram_map[word0] = {word1: math.log(c * count) for word1, count in counts.items()} c = 1. / sum(unigram_map.values()) unigram_map = {word: math.log(c * count) for word, count in unigram_map.items()} max_len = max(map(len, unigram_map)) def optimal_parse(text): word_spans = {j: [] for j in range(len(text) + 1)} for i in range(len(text)): for j in range(i + 1, min(i + max_len, len(text)) + 1): if text[i:j] in unigram_map: word_spans[i].append(j) min_cost = collections.defaultdict(lambda: float('inf')) parent = {} queue = [(0., 0, 0)] while queue: cost, i, j = heapq.heappop(queue) if cost > min_cost[(i, j)]: continue if j == len(text): break if j == 0: word0 = '<s>' else: word0 = text[i:j] for k in word_spans[j]: word1 = text[j:k] if word1 in bigram_map[word0]: word1_cost = -bigram_map[word0][word1] else: #It would technically be more correct to normalize the unigram probability only over unseen words. word1_cost = -(log_p_unseen[word0] + unigram_map[word1]) cost1 = cost + word1_cost if cost1 < min_cost[(j, k)]: min_cost[(j, k)] = cost1 parent[(j, k)] = i heapq.heappush(queue, (cost1, j, k)) words = [] while j != 0: words.append(text[i:j]) i, j = parent.get((i, j)), i return words[::-1] print(optimal_parse('ivehadathoughtandamcurioushowpeoplewouldsolveit'))
abecedarius 5y ago
Short answer in Python: https://stackoverflow.com/questions/195010/how-can-i-split-multiple-joined-words/481773#481773 https://stackoverflow.com/questions/195010/how-can-i-split-m... This version assumes non-dictionary "words" have probability 0. But it's the same basic idea as a fancier answer, and it's quick.

eutectic 5y ago

I would try an n-gram model with dynamic programming. e.g. logp(_, "") = 0 logp(word0, text) = max(logp_bigram(word0, word1) + logp(word1, rest) for word1, rest in prefix_words(text))

gattilorenz 5y ago

"AI" and "simple programming" are not mutually exclusive :) look at the Speech and Language processing book, particularly chapter 3 about language models https://web.stanford.edu/~jurafsky/slp3/ https://web.stanford.edu/~jurafsky/slp3/ You can implement a language model based on character n-grams to calculate whether a sequence is more likely with or without a space. Of course you would need a way of estimating the proability of each sequence, which means you need a corpus to train your language model on.

wodenokoto 5y ago

This is a common problem in Japanese NLP, and while state of the art is using deep learning, almost everyone use dynamic programming or conditional random fields together with a dictionary to solve it. There also exists research on solving this problem unsupervised which basically invents new word boundaries for a language (remember that spoken languages doesn’t have word boundaries - it was invented for writing and strictly speaking, current spelling isn’t the only way to solve word boundaries for a given language)

tester34 5y ago

Have you tried using an ~~XML~~ PDF parser instead? /s and tried to find which sentence without spaces matches your sentence

ghusbands 5y ago

It's worth noting that different PDF-to-text tools (and different PDF-display tools that have text-copying) get different results and it can be worth trying a few. For the most part, the vector parts of a PDF and the association with the text is sufficient to discover spacing information.

deleted 5y ago

[deleted]

epilys 5y ago

It's called word segmentation. There are libraries for it: https://github.com/grantjenks/python-wordsegment https://github.com/grantjenks/python-wordsegment https://github.com/InstantDomain/instant-segment https://github.com/InstantDomain/instant-segment (rust) I used the latter to process pdf plain text output quite successfully.

eutectic 5y ago

I got nerd-sniped and wrote a simple Python solver for this problem. You can find the ngram files at Norvig's site (https://norvig.com/ngrams/ https://norvig.com/ngrams/). import collections import math import heapq with open('count_1w.txt', 'r') as f: unigrams = [l.split() for l in f] unigram_map = collections.defaultdict(lambda: 0) for word, count in unigrams: unigram_map[word] = int(count) with open('count_2w.txt', 'r') as f: bigrams = [l.split() for l in f] bigram_map = collections.defaultdict(lambda: collections.defaultdict(lambda: {})) for word0, word1, count in bigrams: bigram_map[word0][word1] = int(count) log_p_unseen = collections.defaultdict(lambda: 0.) for word0, counts in bigram_map.items(): for word1, count in counts.items(): unigram_map[word1] += count total = sum(counts.values()) #smoothing for unseen words mn, mx = min(counts.values()), max(counts.values()) if mn == mx: p_unseen = 0.5 else: #geometric series approximation r = (mn / mx) ** (1. / (len(counts) - 1)) n = mn * r / (1. - r) p_unseen = n / (n + total) log_p_unseen[word0] = math.log(p_unseen) c = (1. - p_unseen) / total bigram_map[word0] = {word1: math.log(c * count) for word1, count in counts.items()} c = 1. / sum(unigram_map.values()) unigram_map = {word: math.log(c * count) for word, count in unigram_map.items()} max_len = max(map(len, unigram_map)) def optimal_parse(text): word_spans = {j: [] for j in range(len(text) + 1)} for i in range(len(text)): for j in range(i + 1, min(i + max_len, len(text)) + 1): if text[i:j] in unigram_map: word_spans[i].append(j) min_cost = collections.defaultdict(lambda: float('inf')) parent = {} queue = [(0., 0, 0)] while queue: cost, i, j = heapq.heappop(queue) if cost > min_cost[(i, j)]: continue if j == len(text): break if j == 0: word0 = '<s>' else: word0 = text[i:j] for k in word_spans[j]: word1 = text[j:k] if word1 in bigram_map[word0]: word1_cost = -bigram_map[word0][word1] else: #It would technically be more correct to normalize the unigram probability only over unseen words. word1_cost = -(log_p_unseen[word0] + unigram_map[word1]) cost1 = cost + word1_cost if cost1 < min_cost[(j, k)]: min_cost[(j, k)] = cost1 parent[(j, k)] = i heapq.heappush(queue, (cost1, j, k)) words = [] while j != 0: words.append(text[i:j]) i, j = parent.get((i, j)), i return words[::-1] print(optimal_parse('ivehadathoughtandamcurioushowpeoplewouldsolveit'))

abecedarius 5y ago

Short answer in Python: https://stackoverflow.com/questions/195010/how-can-i-split-multiple-joined-words/481773#481773 https://stackoverflow.com/questions/195010/how-can-i-split-m... This version assumes non-dictionary "words" have probability 0. But it's the same basic idea as a fancier answer, and it's quick.