4 ms·

I am guilty as charged of saying impulsively that the first solution is O(n)! The reverse trie is genius, but with dynamic programming do you still need it? I

I am guilty as charged of saying impulsively that the first solution is O(n)! The reverse trie is genius, but with dynamic programming do you still need it? I would say that if in the general setting you can afford O(n^2) preparatory steps, and therefore you can just remember which (start, end) pairs correspond to a valid word with regular trie lookups. That is O(n) steps for each start position, giving a total of O(n^2).

behdad 4y ago
With the dynamic-programming you don't need the reverse trie indeed.
- roflyear 4y ago
  I had a crazy interview question at Google I failed a decade ago. Turns out it was from a PHD thesis. I really hate this questions. It's just stupid.
eesmith 4y ago
Doesn't that confuse two uses of n? One is the length of the word. The other is the number of dictionary elements. If your language is constrained to 1,000 words, then the dictionary will be pretty small and the hash table can be constructed with no chains. That should have constant-time lookup no matter how long the query concatenation is. I don't see why O(n^2) should be optimal. The question is only to determine if a match exists, and that can be expressed as a regular expression. In the following I omit all 1-letter words since my dictionary includes all the letters. >>> words = [line.strip() for line in open("/usr/share/dict/words") if len(line.strip()) > 1] >>> words.sort(key=len, reverse=True) # because Python uses left-to-right match, not longest >>> pattern = "(" + "|".join(words) + ")+$" >>> import re >>> matcher = re.compile(pattern) # takes a few seconds >>> matcher.match("ducksoup") <re.Match object; span=(0, 8), match='ducksoup'> >>> matcher.match("ducksquom") >>> matcher.match("theremanywordsinthisone") <re.Match object; span=(0, 23), match='theremanywordsinthisone'> >>> matcher.match("theremanywordsqinthisone") is None True Python uses backtracking, so this probably isn't O(n), especially with the ability to choose the dictionary. But with there are non-backtracking matchers which would make this O(n). Here's re2 from https://github.com/google/re2 https://github.com/google/re2 : >>> import re2 >>> opts = re2.Options() >>> opts.max_mem = 200000000 >>> matcher = re2.compile(pattern, opts) >>> match = matcher.match("ducksoup") re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54 >>> match.start(), match.end() (0, 8) >>> match = matcher.match("ducksquom") re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54 >>> match is None True This is first time I've used re2. There's probably a way to prevent that warning message - I believe this is falling back to an NFA, which might not be O(n)? Anyway, here it is processing the concatenation of 100,000 words selected at random (I've omitted the warning message): >>> s="".join(random.sample(words, 100000)) >>> len(s) 956249 >>> import time >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? True time: 12.3 seconds >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s+'Q') is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? False time: 12.3 seconds Cut the size by 10 and it's about 10x faster: >>> s="".join(random.sample(words, 10000)) >>> len(s) 95457 >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? True time: 1.3 seconds For this test it appears to be linear in the query size. Edit: if I increase max_mem to 2_000_000_000 then I don't get the warning message. But then the DFA-based search takes 141.5 seconds. That should be O(n) time in the query length, but an order of magnitude slower than the NFA-based search. That's why O(n) analysis isn't enough to really figure out "a faster solution."
- bonzini 4y ago
  In the article n always refers to the length of the string.
  - jonstewart 4y ago
    It does, but the article actually doesn't define n and it's confusing. In the common case, where s is short and the dictionary is big, the size of the dictionary probably matters most to the running time. s is likely a cache line and a handful of instructions to compare — whereas the dictionary probably doesn't fit in L1 or L2, maybe not L3. Obsessing about algorithmic analysis based on the string size instead of the size of the dictionary gives good signal for whether the candidate is a pedant, and poor signal about engineering.
  - eesmith 4y ago
    Hmm. Yes, I misinterpreted this part: > I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²). I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length. That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not". Under Big-O analysis, this is O(1) time.
- burntsushi 4y ago
  Try running the search many times. The lazy DFA should get faster. The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is why. Because it builds itself during the search. A real DFA would be truly O(n) because it would be fully built before starting a search.
  - eesmith 4y ago
jameshart 4y ago
The dictionary words have a fixed, known upper bound to their length. It's a fixed size dictionary. The dictionary lookup can be considered O(1) on this basis alone. But then, that means that my candidate string can only be a maximum of twice the length of the longest dictionary word, so the entire process is O(1). For realistic English words, we're talking about a typical candidate string of length, what, 20 maybe? I need to do somewhere between 19-38 dictionary lookups of 1-19-letter strings to test every splitting of such a word. Why are we even doing big-O analysis here? Only when you start looking at arbitrarily long strings to see if they are word sequences does this analysis even make sense.
jonstewart 4y ago
The reverse trie — i.e., suffix tree (and related suffix array) — is genius. But a good hash table is almost certainly the way to go. Maybe a wicked good engineer can write this algorithm using a suffix array that actually performs faster than a good hash table with a string compare... but most will miss cache and branch mispredict all over the place.
- roflyear 4y ago
  Also can we discuss why we would want someone to write a trie or any of these solutions rather than using something like a dict? If I saw some convoluted solution like this in a PR there better be a really good reason for it.

behdad 4y ago

With the dynamic-programming you don't need the reverse trie indeed.

roflyear 4y ago
I had a crazy interview question at Google I failed a decade ago. Turns out it was from a PHD thesis. I really hate this questions. It's just stupid.

eesmith 4y ago

Doesn't that confuse two uses of n? One is the length of the word. The other is the number of dictionary elements. If your language is constrained to 1,000 words, then the dictionary will be pretty small and the hash table can be constructed with no chains. That should have constant-time lookup no matter how long the query concatenation is. I don't see why O(n^2) should be optimal. The question is only to determine if a match exists, and that can be expressed as a regular expression. In the following I omit all 1-letter words since my dictionary includes all the letters. >>> words = [line.strip() for line in open("/usr/share/dict/words") if len(line.strip()) > 1] >>> words.sort(key=len, reverse=True) # because Python uses left-to-right match, not longest >>> pattern = "(" + "|".join(words) + ")+$" >>> import re >>> matcher = re.compile(pattern) # takes a few seconds >>> matcher.match("ducksoup") <re.Match object; span=(0, 8), match='ducksoup'> >>> matcher.match("ducksquom") >>> matcher.match("theremanywordsinthisone") <re.Match object; span=(0, 23), match='theremanywordsinthisone'> >>> matcher.match("theremanywordsqinthisone") is None True Python uses backtracking, so this probably isn't O(n), especially with the ability to choose the dictionary. But with there are non-backtracking matchers which would make this O(n). Here's re2 from https://github.com/google/re2 https://github.com/google/re2 : >>> import re2 >>> opts = re2.Options() >>> opts.max_mem = 200000000 >>> matcher = re2.compile(pattern, opts) >>> match = matcher.match("ducksoup") re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54 >>> match.start(), match.end() (0, 8) >>> match = matcher.match("ducksquom") re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54 >>> match is None True This is first time I've used re2. There's probably a way to prevent that warning message - I believe this is falling back to an NFA, which might not be O(n)? Anyway, here it is processing the concatenation of 100,000 words selected at random (I've omitted the warning message): >>> s="".join(random.sample(words, 100000)) >>> len(s) 956249 >>> import time >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? True time: 12.3 seconds >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s+'Q') is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? False time: 12.3 seconds Cut the size by 10 and it's about 10x faster: >>> s="".join(random.sample(words, 10000)) >>> len(s) 95457 >>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds") is concatenation? True time: 1.3 seconds For this test it appears to be linear in the query size. Edit: if I increase max_mem to 2_000_000_000 then I don't get the warning message. But then the DFA-based search takes 141.5 seconds. That should be O(n) time in the query length, but an order of magnitude slower than the NFA-based search. That's why O(n) analysis isn't enough to really figure out "a faster solution."

bonzini 4y ago
In the article n always refers to the length of the string.
- jonstewart 4y ago
  It does, but the article actually doesn't define n and it's confusing. In the common case, where s is short and the dictionary is big, the size of the dictionary probably matters most to the running time. s is likely a cache line and a handful of instructions to compare — whereas the dictionary probably doesn't fit in L1 or L2, maybe not L3. Obsessing about algorithmic analysis based on the string size instead of the size of the dictionary gives good signal for whether the candidate is a pedant, and poor signal about engineering.
- eesmith 4y ago
  Hmm. Yes, I misinterpreted this part: > I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²). I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length. That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not". Under Big-O analysis, this is O(1) time.
burntsushi 4y ago
Try running the search many times. The lazy DFA should get faster. The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is why. Because it builds itself during the search. A real DFA would be truly O(n) because it would be fully built before starting a search.
- eesmith 4y ago

jameshart 4y ago

The dictionary words have a fixed, known upper bound to their length. It's a fixed size dictionary. The dictionary lookup can be considered O(1) on this basis alone. But then, that means that my candidate string can only be a maximum of twice the length of the longest dictionary word, so the entire process is O(1). For realistic English words, we're talking about a typical candidate string of length, what, 20 maybe? I need to do somewhere between 19-38 dictionary lookups of 1-19-letter strings to test every splitting of such a word. Why are we even doing big-O analysis here? Only when you start looking at arbitrarily long strings to see if they are word sequences does this analysis even make sense.

jonstewart 4y ago

The reverse trie — i.e., suffix tree (and related suffix array) — is genius. But a good hash table is almost certainly the way to go. Maybe a wicked good engineer can write this algorithm using a suffix array that actually performs faster than a good hash table with a string compare... but most will miss cache and branch mispredict all over the place.

roflyear 4y ago
Also can we discuss why we would want someone to write a trie or any of these solutions rather than using something like a dict? If I saw some convoluted solution like this in a PR there better be a really good reason for it.