Friday, February 3, 2017

Hashing and Probability of Collision

Problem D of Codeforces #395 required hashes of rooted trees. In this post I give some examples of good hashes and bad hashes, and then construct a good hash for rooted trees.

The most well-known hash in competitive programming is probably the rolling-hash of strings. The following problem looks stupid, but let's solve it using rolling hash anyway.

Problem 1. You are given two strings s, t of lengths N (<= 10^5) that consist of lowercase letters. Determine if they are the same.

Let MOD=10^9+7. Choose an integer r uniformly at random from the interval [0, MOD). Compute the sum of r^i * s[i] over all i. This is called the rolling hash of s. We can consider it as a polynomial of r, let's denote it as S(r). Similarly, define T(r). The hash collision happens when s and t are different strings (thus S and T are different polynomials), but unluckily S(r) = T(r). Here we use Schwartz-Zippel lemma:

Let P(x_1, ..., x_k) be a non-zero (multi-variable) polynomial on a finite field F_MOD. If the variables are chosen independently and uniformly at random, the probability that P(x_1, ..., x_k) = 0 is at most D/MOD, where D is the total degree of the polynomial.

In the case of rolling hash, we are only interested in single-variable polynomials. From the lemma above, we can prove that the collision probability is at most N/MOD (<= 1/10^4). Thus I'd say this is a "good hash". My intuition tells that in practice the probability is as small as 1/MOD, but that looks at least very hard to prove. Let me give an interesting example that shows the intuition is not always correct. In the lemma F_MOD must be a field, and MOD must be a prime. What happens if the modulo is not prime, for example 2^64 (this would simplify the implementation). It turns out that the rolling hash doesn't work well for a certain case if the modulo is 2^64. Detailed description on Codeforces.

Problem 2. You are given two graphs G, H with N (<= 10^3) vertices and M (<= 10^4) edges. Determine if they are isomorphic.

For each vertex v in the graph and an integer d, define the level-d hash for v, h(d, v). When d = 0, define h(0, v) = 1. Otherwise, let x_1, ..., x_k be the sorted list of level-(d-1) hashes of vertices adjacent to v, and define h(d, v) as the sum of x_i * r^i modulo MOD. Compute the level-N hashes of the two graphs for each vertex, sort them, and compare them.

It looks very hard to find a testcase against this hash. (Actually no - see Petr's comment below). However there's no theoretical guarantee under this hash and I think most people agree that this doesn't look valid as an intended solution of a problem in a contest (graph isomorphism is a well-known difficult problem). I'd say this is a "bad hash".

OK, now we want to construct a good hash for rooted trees. Before that, let's try an easier version. Hashes for (multi)sets.

Problem 3. You are given two (multi)sets A = {a_1, ...., a_n} and B = {b_1, ..., b_n}. n <= 10^5 and each element is in the interval [0, MOD). Determine if they are the same.

One possible solution is to sort the input and then compute the rolling hash of it. Can you find a linear-time hash? The solution is indeed very simple. Let's take a random integer r from the interval [0, MOD), and compute the hash (r+a_1)(r+a_2)...(r+a_n). This is a polynomial of r of degree n, so again from Schwartz-Zippel lemma, the collision probability is at most n/MOD.

Problem 4. You are given two rooted trees with n vertices. Determine if they are isomorphic.

Like previous examples, we assign a polynomial for a rooted tree, and evaluate the polynomial for random variables. However, unlike previous examples, this time we use multi-variable polynomials. We define the polynomial P(G) for a rooted tree G as follows. If G is a single leaf, P(G) = 1. Otherwise, let d be the depth of the tree, k be the number of children of the root of G, and G_1, G_2, ..., G_d be the subtrees corresponding to those children. Define P(G) = (x_d + P(G_1))(x_d + P(G_2))...(x_d + P(G_k)). See the picture for an example. (x_1, x_2, x_3 are replaced with x, y, z).

This way we get a multi-variable polynomial over d variables of degree l, where l is the number of leaves in the tree. We can prove that two polynomials that correspond to non-isomorphic trees are different (by using the uniqueness of factorization of the ring of polynomials). Thus, if we evaluate this polynomial for random variables, we get a good hash with collision probability at most l/MOD!


10 comments:

  1. Awesome explanation!

    For graph isomorphism, it's easy to break such hashing: take two non-isomorphic regular (all degrees the same) graphs.

    ReplyDelete
    Replies
    1. Thank you for pointing out, I'll fix it.
      Maybe computing hashes of graphs of this size is hard even in practice.

      Delete
    2. Hello, I am Theresa Williams After being in relationship with Anderson for years, he broke up with me, I did everything possible to bring him back but all was in vain, I wanted him back so much because of the love I have for him, I begged him with everything, I made promises but he refused. I explained my problem to my friend and she suggested that I should rather contact a spell caster that could help me cast a spell to bring him back but I am the type that never believed in spell, I had no choice than to try it, I mailed the spell caster, and he told me there was no problem that everything will be okay before three days, that my ex will return to me before three days, he cast the spell and surprisingly in the second day, it was around 4 pm. My ex called me, I was so surprised, I answered the call and all he said was that he was so sorry for everything that happened that he wanted me to return to him, that he loves me so much. I was so happy and went to him that was how we started living together happily again. Since then, I have made promise that anybody I know that have a relationship problem, I would be of help to such person by referring him or her to the only real and powerful spell caster who helped me with my own problem. email: {drogunduspellcaster@gmail.com} you can email him if you need his assistance in your relationship or any other Case.

      1) Love Spells
      2) Lost Love Spells
      3) Divorce Spells
      4) Marriage Spells
      5) Binding Spell.
      6) Breakup Spells
      7) Banish a past Lover
      8.) You want to be promoted in your office/ Lottery spell
      9) want to satisfy your lover
      Contact this great man if you are having any problem for a lasting solution
      through {drogunduspellcaster@gmail.com}

      Delete
  2. "It turns out that the rolling hash doesn't work well for a certain case if the modulo is 2^64. Comments in Russian." Comment link is broken Can you please fix it.
    Thanks

    ReplyDelete
    Replies
    1. I found an English description: http://codeforces.com/blog/entry/4898

      Delete
    2. It's not exactly broken, just change the language in codeforces to russian and click the link again :)

      Delete
  3. "and G_1, G_2, ..., G_d be the subtrees corresponding to those children"

    I think it should be G_1, G_2, ..., G_k. Am I right?

    ReplyDelete
  4. I NEED MY EX LOVER BACK Contact: Unityspelltemple@gmail.com ,Is certainly the best spell caster online, and his result is 100% guarantee. My Names is Julie Collins from United states. After 12years of marriage, me and my husband has been into one quarrel or the other until he finally left me and moved to California to be with another woman. I felt my life was over and my kids thought they would never see their father again. i tried to be strong just for the kids but i could not control the pains that torments my heart, my heart was filled with sorrows and pains because i was really in love with my husband. Every day and night i think of him and always wish he would come back to me, I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a (Love spell) for me. 28 hours later, my husband really called me and told me that he miss me and the kids so much, So Amazing!! So that was how he came back that same day,with lots of love and joy,and he apologized for his mistake,and for the pain he caused me and the kids. Then from that day,our Marriage was now stronger than how it were before, All thanks to Dr Unity. he is so powerful and i decided to share my story on the internet that Dr.Unity real and powerful spell caster who i will always pray to live long to help his children in the time of trouble, if you are here and you need your Ex back or your husband moved to another woman, do not cry anymore, contact this powerful spell caster now. Here’s his contact: Email him at: Unityspelltemple@gmail.com , you can also call him or add him on Whats-app: +2348071622464 , you can also visit his website: https://urgentspell.blogspot.com .

    ReplyDelete
  5. How to get your ex back and save your relationship or marriage! contact: Unityspelltemple@gmail.com , Is certainly the best spell caster online, and his result is 100% guarantee. I'm so excited my boyfriend is back after he left me for another girl. After 4 years of relationship with my boyfriend, he broke up me and brought in another Girl, i did all i could to get him back but all proved abortive, I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a (Love spell) for me. 28 hours later, my boyfriend really called me and told me that he miss me so much, So Amazing!! So that was how he came back that same day,with lots of love and joy,and he apologized for his mistake, and for the pain he caused me . Then from that day, Our relationship was now stronger than how it were before, All thanks to Dr Unity. he is so powerful and i decided to share my story on the internet that Dr.Unity real and powerful spell caster who i will always pray to live long to help his children in the time of trouble, if you are here and you need your Ex back or your husband moved to another woman, do not cry anymore, contact this powerful spell caster now. Here’s his contact: Email him at: Unityspelltemple@gmail.com , you can also call him or add him on Whats-app: +2348071622464 , you can also visit his website: https://urgentspell.blogspot.com.

    ReplyDelete
  6. Excited, My Girlfriend Is Back Contact Happylovespell2@gmail.com.. My Ex and I have been getting into little arguments which then later escalated. A lot of which are my fault but I never thought I would lose her because we are in love. She told me yesterday that she loves me but she done. That the fights keep hurting her too much. I can’t believe I hurt her like that and would love nothing more than another chance to prove to her and myself that I will cut out my insecurities that I’ve brought into this relationship. I did all i could to end this fight between us, didn’t work so i had to seek the help of a spell caster who i met online and promised to help me bring her back into my life in 2 days time. i wasn’t really sure about this, but i was really desperate that i had to do all that the spell caster asked me. it was on the second day at 5pm on Friday, i had a knock on the door and to my greatest surprise, it was my girlfriend, the first thing she said, was that she has forgiven me and she will never leave me again, Am so full of joy for what this spell caster and to this product page and graphic love spell coz it really help and work for me, i also want the world to benefit from this. if you need his help you can reach him for any thing on relationship problem, getting your ex back save and protect your marriage life with your soul mate contact him now for he is so powerful and real. Urgently email him now
    @.... happylovespell2@gmail.com
    You can also view on his Blogs site... https://happylovespell2.blogspot.com.ng/
    Also for quick option on how to help with a love spell add him up on Whats-app +2348133873774

    ReplyDelete