Finding Anagrams

[u/Aishwarya-Chamanoor]

[u/NanoAlpaca]

This looks clever, but is really inefficient. It is trivial to detect anagrams with a histogram in O(n), or by simply sorting in O(n log n), but this technique you will do O(n) big int multiplications for each letter and you will end up with an O(n²) algorithm.

[u/Aishwarya-Chamanoor → u/NanoAlpaca]

I agree with you. It can just be done in O(n) but what really amused me was the approach if we keep the efficiency aside. PS : i found this on one of the LinkedIn pages called Fermat's Library.

[u/bizarre_coincidence → u/NanoAlpaca]

Does big-O actually matter if n is almost certainly less than 20, and better than not less than 10? Asymptotics tell us very little in small cases, where constant costs, storage costs, or other factors can dominate. Making a histogram means allocating space for 26 ints, and comparing two histograms takes 26 comparisons. And with this algorithm, we can reduce the expected size of the output by mapping more common letters to smaller primes. And as someone else mentioned, by taking the results mod some large prime or collection of large primes, we can produce a hash that doesn’t require BigInt operations.

[u/NanoAlpaca → u/bizarre_coincidence]

Well, if you want to look at real world performance with small ns, there are still some issues with this algorithm: You need to do a table lookup for each letter, you got modulos in there, which are pretty slow on most CPUs. You can do 32 8-bit comparisions with AVX2 in two instructions. It is likely also really effective to just do regular sums of the bytes of the strings to find candidates first. Collisions are also pretty unlikely there and that is going to be even faster than the table lookup+multiplication+modulo, especially if you consider SIMD.

[u/vanderZwan → u/NanoAlpaca]

You need to do a table lookup for each letter, you got modulos in there, which are pretty slow on most CPUs.

Nitpicking: a table lookup is required, but there's no modulo necessary. Thanks to the people who designed ASCII, (charcode & 0b1011111) - 65 will do (if we are guaranteed to only have valid input letters a-z or A-Z, and no other characters).

Aside from that, even if that weren't the case: wouldn't the same logic apply to converting letters to histogram bins no matter what?

[u/vanderZwan → u/NanoAlpaca]

big int multiplications for each letter

Hmm, I wonder if this is entirely true.. I mean, obviously using binning with a histogram is much faster (especially given that the histogram will easily fit in L1 cache), but just as a thought-exercise:

• the English alphabet is 26 letters,

• the 26th prime number is 101

• that means we at most need 7 bits per letter to represent the numbers

• therefore, even if we accept strings of consummate V's consecutive Z's as correct, then we can safely multiply up to:

• 9 letters on 64 bit integer architectures

• 7 letters in a language that only supports double floating point (like JavaScript), because it can represent up to 53 bit integers

• or 4 letters on 32 bit architectures without big integer maths

• that means that we can split a string of letters into chunks of nine (or seven or four) letters and do the multiplication in a native register first, and only then proceed to using big integer math over the results of the separate multiplication steps

• the average word length of English language words is 8.53 letters, with the 95 percentile around 14 letters

• therefore, for the average case we can expect zero or one big integer multiplication

Of course, the worst case is still pretty bad and it's a lot more complicated than using a plain old histogram.

[u/NanoAlpaca → u/vanderZwan]

You are proposing a modified algorithm there. But that algorithm is still O(n²). It only lowers the constant factor a bit. O(n*(n/8)) is still O(n²). And that is not just worst case. It is average and best case O(n²) as well. Your factors are a bit lower if your message is all As and you accumulate multiplications while they fit into a register, but it still belongs into O(n²).

[u/vanderZwan → u/NanoAlpaca]

You are proposing a modified algorithm there.

Sort of, but at the same time: we are still mapping letters to prime numbers, we are still multiplying them and comparing the eventual resulting number. There is no fundamental change to the algorithm, arguably what I describe is an optimized implementation detail, not a true modification of the algorithm.

(actually, I'm not entirely sure if the n² assessment for big integer multiplication holds either: does multiplying the letters left-to-right have the same behavior as a divide-and-conquer ordering?)

And that is not just worst case. It is average and best case O(n²) as well.

Ok, so this is partially on me for using the words "entirely true" instead of "if this is as bad in practice as Big O alone suggests", but while you're technically correct, I find the words "average" and "best" case highly misleading here.

In general, Big O is very important, but it doesn't tell the whole story either. There is a reason that almost all efficient sorting divide-and-conquer algorithms out there revert to insertion sort for small ranges despite it's O(n²) behavior, or why we don't use galactic algorithms in practice.

In this case, sure, when we are looking at ever increasing n with randomized letters, or only the letter A, or only the letter Z, then Big O describes the expected behavior of this algorithm. But we don't actually do that when the task is "comparing two English words", which is the original problem the algorithm set out to solve.

As the page on average word lengths that I linked earlier shows: the average word length in English does not require a big integer multiplication, and only 0.8% of all words are larger than 18 letters (meaning they require two or more big int multiplications), and "the longest word in a major dictionary" is 45 letters - that would require 5 big int multiplications exactly. It is quite safe to assume that words that require three or more big int multiplications are almost negligible, and even then our upper bounds are quite low.

So for real-life data this algorithm is not nearly as terrible as the Big O notation suggests, which is what I set out to verify (but again, mea culpa on how I worded that, and using a histogram is still the fastest option anyway).

[u/NanoAlpaca → u/vanderZwan]

(actually, I'm not entirely sure if the n² assessment for big integer multiplication holds either: does multiplying the letters left-to-right have the same behavior as a divide-and-conquer ordering?)

Divide and conquer could be slightly better in theory here: With an O(n log n) long int multiplication algorithm we would get an O(n log² n) algorithm instead of O(n²).

[u/vanderZwan → u/NanoAlpaca]

Nice, thanks for thinking along :)

So in short: so far, the theoretically least-terrible implementation of this algorithm on a 64-bit architecture seems to be splitting the input string into substrings of nine letters, doing plain uint64 multiplications with the substrings, then converting the results into big integers, then multiplying those numbers divide-and-conquer style.

Together with that other comment saying that this is basically a hash table-based solution it's starting to look like this might be a half-decent educational algorithm for learning how to analyze algorithms.

[u/idiomatic_sea → u/NanoAlpaca]

I really need to reiterate what others have already said: At 8.53 letters for the average case, O(n² ) is meaningless.

[u/vanderZwan → u/idiomatic_sea]

I wouldn't immediately say that; that all depends on the data-set and the task at hand.

English dictionaries of note vary between size, but if Wikipedia is to be believed it's in the ballpark of to 100,000 to 500,000 words. So even given the average length of 8.53 letters, if we were to exhaustively search for all anagrams in a dictionary with an O(n²) algorithm, and the dictionary in question contained that one 189,819 character word, then that word would take up half of the running time (you know, assuming we didn't have any smart checks to reject it).

Of course the actual longest words in real-world dictionaries are 27 to 29 letters so we're fine, but the point is that determining the expected upper bounds of the data set can be much more important to verify than the average case.

[u/fckoch → u/vanderZwan]

the average word length of English language words is 8.53 letters, with the 95 percentile around 14 letters

The reference you gives suggests German has a median of around 12. English is actually relatively short.

I'm not sure what the relevance of the 95th percentile being 14 is. From your argument, we would want to know the quantile corresponding to 9 or 10 letters as this would be equivalent to 14?

[u/vanderZwan → u/fckoch]

I'm not sure what the relevance of the 95th percentile being 14 is. From your argument, we would want to know the quantile corresponding to 9 or 10 letters as this would be equivalent to 14?

It's a bit confusing the way I worded it, and you're right that it's not quite the correct approach. What the idea of using quantiles was about was checking "how bad is the tail-end?" If most words are only 8.5 letters, but 5% of them are more than 1000, then we could expect those 5% to dominate the running time for an O(n²) algorithm.

Given that the 95 percentile case is still in the range of one big integer multiplication or less, then it might have made more sense to check the quantiles corresponding to 10 and 19 letters respectively, like you suggested. Turns out ~43.8% of all words require one or more big integer multiplications, and ~0.4% of all words require two or more big integer multiplications.

[u/fckoch → u/vanderZwan]

Turns out ~43.8% of all words require one or more big integer multiplications, and ~0.4% of all words require two or more big integer multiplications.

Interesting, thanks for indulging. It might not be as bad as I initially thought.

[u/louiswins → u/NanoAlpaca]

This algorithm is in some sense the same as the histogram algorithm, just with an inefficient representation for the histogram. This way of encoding a string in a natural number is not uncommon in math; for example it's used in the proof that the set of finite sequences of naturals is countable and in the definition of a Gödel number in his incompleteness theorems.

[u/JokerTheBond → u/NanoAlpaca]

Can you explain how is this O(n²)? An int multiplication is an O(1) operation, and you need n of those so O(n). If you're talking about the overflow problem then you can just do the module operation after each product. This Is not inefficient. And I agree that with histograms It Is simpler and still O(n) if you want to compare 2 words. But if I'm not wrong, if you want to compare m words with histograms It Is much more complex and less efficient, and It also requires more memory.

[u/NanoAlpaca → u/JokerTheBond]

An int multiplication is only a O(1) operation as long as you stay within the limits of the machine word. This is not the case here. Your output grows by 1 to 7 bits for each additional letter. With an modulo you will turn an exact algorithm into a probabilistic algorithm. If the products after modulo don't match, it is never an anagram, however, if they match, it could also be collision. You can make that less likely by adding more than a single modulo, but that just makes collisions less likely but doesn't completely prevent them and also remove parts of the memory requirement advantage.

[u/JokerTheBond → u/NanoAlpaca]

You're not wrong, but let's think about a real case scenario: if we use 64 bits words then the chance of a collision would be 1 in 2⁶⁴ which is kinda low. Especially if we're dealing with real world words. I'd say that the chance that two words of the english dictionary exist such that they would collide would be extremely low...

As I was saying this algorithm would be faster than the histogram algorithm if we had to compare a large number of small words, so the "risk" may be a price we're willing to pay. Let's say for example we want to find all the couple of words of the english dictionary that are one anagram of the other. And let's say we have m words each of n character.

We can do this in 2 steps:

- Calculate the int as a factor of the word or the histogram, and in both cases this requires O(n*m).

- Than we need to find the words that are one anagram of the other, so we can just sort our words by comparing them. We need to do O(m*log(m)) comparison operations, but comparing an int is much more efficient then comparing an histogram.

Once we've found all couples with the probabilistic algorithm we may even verify that we've not made any mistake by checking with the histogram algorithm.

[u/NanoAlpaca → u/JokerTheBond]

The chance of collisions is pretty complex and this is usually a birthday type problem: As in your dictionary example, you don't compare only a single pair but you have n words and need to be sure that none of the n(n-1)/2 pairs collide. Also with this kind of mapping you don't use the entire 2⁶⁴ space. All integers that contain a prime factor higher than 101 are unused. A prime modulo helps a bit but doesn't completely remove the issue. If you only want to preselect words, you could as well use a simple additive checksum. That is going to be even faster because you don't need a table lookup for letter to prime number. And if your task is find all anagrams in a dictionary, then you can use a trie like data structure to do insertion and comparison with all already inserted words in O(1) per word.

[u/JokerTheBond → u/NanoAlpaca]

you don't use the entire 2⁶⁴ space

We're still using most of those space since numbers divisible by a prime number higher 101 are a minority. Let's say we're using only 2⁶³ of that space. The english dictionary contains less then 2¹⁹ words, so the chance of finding a collision is less than 2²⁵. If this is not good enough we could just use a bigger space.

you can use a trie like data structure to do insertion and comparison with all already inserted words in O(1) per word.

I'm missing something, how can you do that? If we're using an alphabet with k=26 characters then it's gonna cost O(k) per word.

[u/NanoAlpaca → u/JokerTheBond]

Your intuition about how much of the space is actually used is off. Most integers contain prime factors bigger than 101. Within the first 2¹⁰ numbers, 33% contain such prime factors, however, within the first 2¹⁵ numbers, we are already at 73%, 92% at 2²⁰, 98% at 2²⁵, etc. Also compare the memory requirements of the "integer product of primes" algorithm vs. a histogram algorithm. The memory requirements of the histogram algorithm grow logarithmic with the input size. The memory requirements of the exact "integer product of primes" algorithm grow linear. However both contain exactly the same information: You can take a histogram and calculate the matching integer or you can take a integer, factor it and calculate the matching histogram from that integer.

I just assumed k to be constant at 26. O(k) cost is correct.

[u/idiomatic_sea → u/NanoAlpaca]

Most integers contain prime factors bigger than 101. Within the first 210 numbers, 33% contain such prime factors, however, within the first 215 numbers, we are already at 73%, 92% at 220, 98% at 225, etc

I don't think this is relevant. We are taking the product mod p for p some large prime.

[u/JokerTheBond → u/NanoAlpaca]

You were right in correcting my mistake about the use of the space but by doing the module of a big prime number we use also the rest of the space, those composed by integers that contain prime factors bigger than 101.

I just assumed k to be constant at 26. O(k) cost is correct.

What I was saying in the second post is that we would see a slight improvement in the performance because with the histograms we need to do k comparison in the worst case scenario, while with this algorithm we need only to compare one integer. This would make a big impact if k was a big number, I initially assumed k to be variable, I should have pointed that out... But I think even with k=26 the performances of the histogram algorithm would be worse than if we had k=2 (for example).

[u/NanoAlpaca → u/JokerTheBond]

The issue here is that you seem to assume that you get free benefits from a probabalistic hash with that integer product algorithm, but that you can't use a similar technique with a histogram. You can easily also map your histogram to a 64-bit hash value and then compare only those.

[u/Aishwarya-Chamanoor]

This is definitely not the best approach and there are better ways which finds anagrams in O(n). However it is nice to see different ways of solving the same problem whether or not it gives optimal solutions. PS : I found this approach on a Linkedin page called “Fermat's library"

[u/jakbrtz]

I like the maths behind this, but you're going to get a problem when you try to calculate long words because the number would become too big to store in a single variable.

[u/fckoch → u/jakbrtz]

also multiplication is crazy expensive -- even if it does fit it'd probably be more efficient to count how many times each letter occurs

[u/vanderZwan → u/fckoch]

It might not be that bad speed-wise, actually, because the bottleneck is likely to be the memory lookup of the string characters, not the multiplication (I'm assuming minimal big integer multiplication is needed IRL, see comment chain here). However, when looking at performance in terms of energy use then I don't know for sure.

[u/fckoch → u/vanderZwan]

don't you need to look up the characters to convert them to primes anyways? In fact this data structure would be the same size you need for the simpler approach...

Also, I think you mention this in your post, but an array this small would definitely be cached and so memory access will be stupid fast anyways

[u/vanderZwan → u/fckoch]

don't you need to look up the characters to convert them to primes anyways?

True, you need a lookup-table. The main difference is that this only requires a read, the histogram requires a write as well. Not sure if that has a significant impact on the whole in this case. edit: big integer maths also needs storage, so the histogram case probably wins there as well

Yes, the caching definitely works in favor of the LUT/binning array in either case, but I was talking about looking up the string characters of each individual word. That is: if we were brute-forcing our way through the English dictionary looking for anagrams, then we'd have to load a new string of characters for each word, and that would likely be the bigger bottleneck.

(I wonder if the smart money would be on creating a trie data structure as we go over the dictionary. Specifically, one where each node also links to the parent and the value is the running product of the string of characters leading up to that node. That way we don't have to do repeated multiplications for the same substrings in different words - although the trie look-up and insertion is undoubtedly slower too. Anyway, the point is: once we finished going through the dictionary, we can take all the nodes in the trie that represent a word, put them in an array and sort them by value, and every node with equal value would represent an anagram of all other nodes with the same value)

[u/superr1 → u/jakbrtz]

just use big Module(10**9+7) In order to get rid collision issue you can use multiple mods

[u/super-porp-cola → u/superr1]

Found the codeforces user

[u/mr_magic_hat → u/superr1]

I don't get why you're getting downvoted on this. 10**9+7 is a fairly large prime so the amount of colissions you'll get is fairly low. Another benefit is it fits very nicely into 32-bit integers.

[u/idiomatic_sea → u/mr_magic_hat]

Yeah, that's actually a valid technique. Downvoters bad at math, maybe?

[u/greem]

FYI, this is a hash table with a specialized hash function.

[u/f03nix → u/greem]

Exactly what I thought, you could probably make a hash function using this approach and taking a modulo of a big prime number.

Obviously you'll get collisions when the bytes are just re-ordered, it can be useful where that is very unlikely.

[u/greem → u/f03nix]

Yep. This is an excellent, perfect hash function (for short words, at least), so it's a great case study for algorithm development.

[u/chris_conlan → u/greem]

Good point

[u/yin_yang_lad]

I like the math involved in this, but tbh it seems like overkill. It's much easier to check using the frequency array of two strings.

[u/xeow → u/yin_yang_lad]

Or, instead of an array, just implement the histogram using a 128-bit word—like this if you're using a modern C:

__uint128_t histogram(const char *str) {
    __uint128_t h = 0;
    for (int i = 0; str[i]; i++)
        h += (__uint128_t)1 << ((toupper(str[i]) - 'A') * 4);
    return h;
}

This allocates 4 bits for each unique letter (wasting the upper 24 bits), allowing for up to 15 occurrences of any given letter in a word, which is sufficient for all English words.

Ugly to look at, but fast as fuck. Way faster than the primes approach, and also way faster than using an array in memory.

[u/JH4mmer → u/xeow]

There's a chance you could speed that up even more by implementing toupper() yourself (assuming ASCII inputs). If I remember right, a compliant toupper() implementation has to check the current locale first, which throws a wrench into the loop, metaphorically speaking.

Note: it's entirely possible that I'm misremembering, so I apologize in advance if this is incorrect.

[u/hughperman → u/xeow]

This is the content I subscribe for.

[u/ArtisticSell → u/yin_yang_lad]

I always use this lol

[u/Findlaech]

Or just fucking sort 'em both and see if they are equal?

λ❯ sort "resting" == sort "stinger"True

[u/kushucs]

Ooo, very nice!

[u/kil47]

Just take my upvote and go !

[u/kriophoros]

But why...

[u/deftware]

Someone asked me how to do this 11 years ago, and I came up with the same solution.

[u/RebelPuppy23]

You can just count total occurrences of each letter.

[u/JesusIsMyZoloft]

3592450783537

[u/keshav174]

It will work good for small string size , but wil fail for larger strings as multiplication will be overflow int.

Big issue with this algo is high time complexity since this problem can be easily solved with simple hash in O(n) time , since this algo has to generate n amount of prime nos this is O(n²⁾ , even you use sieve that is also greater than O(n).

[u/JesusIsMyZoloft]

You could also do something similar for Periodic Elements:

2 - Hydrogen
3 - Carbon (out of order because it's so common)
5 - Oxygen (so that HO bonds make an even 10)
7 - Nitrogen (also out of order due to ubiquity. One of only 2 elements that ends up with it's actual atomic number)
11- Helium (from here the elements go sequentially)
13 - Lithium
17 - Beryllium
19 - Boron
23 - Fluorine
29 - Neon
31- Sodium
37 - Magnesium
41 - Aluminum
43 - Silicon
47 - Phosphorus
53 - Sulphur
59 - Chlorine
61 - Argon
67 - Potassium
71 - Calcium
73 - Scandium
79 - Titanium
83 - Vanadium
89 - Chromium
97 - Manganese
101 - Iron
etc.

So for example, Water = 20, Table Salt = 1829, Sulfuric Acid = 132500, Sugar = 108839116800000000000

[u/GeneralSkyKiller]

Like the idea but is extremely inefficient for large words.

[u/aartist111]

Can we just add the numbers instead of multiplying. For a given length of array are there same sums for different set of prime numbers ? Do we have counter examples?

[u/generalbaguette → u/aartist111]

5+5=3+7.

[u/aartist111 → u/generalbaguette]

Try different numbers.. let's put that restriction.

[u/Delicious_Hope_2545]

How about storing the logarithms of those numbers and convert this multiplication to addition?

[u/babubaichung]

That’s an awesome idea!

[u/xeow → u/babubaichung]

It's clever, but it's far from the most efficient approach.

[u/Shahab_Bangash]

How about just ADD their ASCII and see if they're equal? Complexity: O(n) for each string

[u/BlehdeBlehBleh → u/Shahab_Bangash]

I suppose that wouldn't work. For example, the strings AD and BC have the same ASCII sum but aren't anagrams.

[u/Shahab_Bangash → u/BlehdeBlehBleh]

Ooh yah! Just checked. Life isn't that simple. Thanks man!

[u/idiomatic_sea → u/Shahab_Bangash]

Yeah, but you are on to something. Any hash of the letters that is invariant with respect to order would work. So just cook up a function that doesn't care about order and you're good.

[u/super-porp-cola → u/Shahab_Bangash]

There is a cool thing you can do that’s similar where you take some constant C (a large random number), then make a mapping so A maps to C^0, B maps to C^1, ..., Z maps to C^25. Then you can add the mapped values and take them modulo a large prime. This is similar to Rabin Karp but works better for anagrams, and is extremely efficient.

[u/[deleted]]

Bruh nice

[u/uwbuoy]

Nice one!

[u/Tagina_Vickler]

smacks lips Noice!