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!


23 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
    3. REAL POWERFUL LOVE SPELL THAT WORKS IN 24 HOURS CALL DR. UGO WONDERS +13863369876

      Hello Everyone here I am Doris by name and i just want to share with you a miraculous testimony, which is so unbelievable until now. How Dr. UGO of generalspelltemple@gmail.com helped me after trying to get my relationship with my husband back. i tried alot of spell casters without any result. I was not my self again, i felt so empty inside me, my love and financial situation became worst until the day a friend of mine in my office told me much about Dr. UGO WONDERS and how powerful he is,so i contacted him for help and told him the problem i was facing and i did what he asked of me. 24 hours after i contacted Dr. Ugo for help which he assured me, I received a call from my husband asking for my forgiveness. i was so surprised because it was a dream come true. i am so happy to have my husband back to me. Thanks to Dr. UGO WONDERS for saving my marriage. if you wish to contact him for urgent solution to your relationship problem, you can contact Dr. Ugo through his direct email address generalspelltemple@gmail.com or call him directly on +13863369876 website: http://generalspelltempleblog.wordpress.com

      You can also contact Dr. Ugo for any of the below problems and be free through his help immediately

      1. Bring back lost lover, even if lost for a long
      time
      2. Stop your marriage or relationship from
      breaking apart
      3. Get promotion you have desired for a long time at work or in your career.
      4. Remove the black pot that keeps on taking your money away
      5. Find out why you are not progressing in life and the solution
      6. Eliminate in family fights
      7. Ensure excellent school grades even for children with mental disabilities
      8. Remover bad spells from homes, business and customer attraction
      9. I destroy and can send back the Nikolos if requested
      10. We heal barrenness in women and disturbing menstruation
      11. Get you marriage to the lover of your choice
      12. Guarantee you win the troubling court cases & divorce no matter how what stage
      13. Ensure success in work and business
      14. Mental illness & bewitched
      15. Can’t sleep at night or walking at night
      16. Recover stolen property
      Once again you can contact him through his direct email address generalspelltemple@gmail.com or call him directly on +13863369876 website: http://generalspelltempleblog.wordpress.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
  7. URGENT EFFECTIVE LOVE SPELL TO GET YOUR EX BOYFRIEND/GIRLFRIEND BACK FAST! Contact: Unityspelltemple@gmail.com is certainly the best spell caster online and his result is 100% guarantee.. My husband breakup with me and left me to be with another woman, and i wanted him back. I was so frustrated and i could not know what next to do again, I love my husband so much but he was cheating on me with another woman and this makes him break up with me so that he can be able to get married to the other lady and this lady i think use witchcraft on my husband to make him hate me and my kids and this was so critical and uncalled-for,I cry all day and night for God to send me a helper to get back my husband!! 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 so much, Oh My God! i was so happy, and today i am happy with my man again and we are joyfully living together as one big family and i thank the powerful spell caster Dr.Unity, he is so powerful and i decided to share my story on the internet that Dr.Unity is best spell caster online who i will always pray to live long to help his children in the time of trouble, if you are here and your lover is turning you down, or your husband moved to another woman, do not cry anymore, contact this powerful spell caster Dr.Unity on his email: 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 ,
    Olivia Stephen
    from North Carolina .

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. Hello, am here not only to testify but also to encourage people facing marital or relationship issue. About the marvelous works of Dr. Ogundu, email: drogunduspellcaster@gmail.com i was lost in love with my husband until a lady snatched him away from me. then i cried out to my friend and she told me about how she faced a similar problem and gave this great man contact to me and i provided all the items he needed for the spell and now am happy again living in love with my family. I employ you to contact this man. Your story or pain’s will change within days and you will be smiling like me today. Once again am grateful. Contact him on his email via: drogunduspellcaster@gmail.com if you are facing any form of problem
    1. Getting your lover or husband back
    2. Money spell/good luck spell
    3. If you want to stop your divorce
    4. Protection spells
    5. Get a job spell
    6. Promotion spells
    7. Getting your money back.
    8. weight loss spell
    9. Love spell
    10. If you want to satisfy your partner/ cure for weak erection
    11. HIV cure

    ReplyDelete
  10. How to get your ex lover back & save your marriage fast "I suggest you read this."?
    I got a divorce from my husband when I was six months pregnant with my second child. We had been arguing and quarreling nonstop since the day our first child was conceived, no love nor trust from him anymore so he divorced me. And all these whiles, I have been trying all different means to get him back, I also tried some different spell casters here in the United States, but none of them could bring Richard back to me. It was only Dr. Unity who guaranteed me an urgent 28 hours spell casting, and he assure me that my husband will be with me again. I am writing to offer my thanks and deep gratitude to you for keeping your promises, and for using your gifted and great powers to bring him back home. I was thrilled to know that you are specialized in reuniting Lovers. Thank you Sir, for helping me through the worst times of my life, for being such a great spell caster, and for giving me a love spell that has brought me so much joy in my marriage. My husband is back and promise never to leave me again. If you doubt his ability, trust me. You should take a chance. It pays off in ways you could never even imagine. If you are thier right now and you need a powerful and urgent love spell to bring back your ex kindly contact Dr. Unity right now he is the only answer to restore your broken relationship or marriage. Here’s his contact: Email him at: Unityspelltemple@gmail.com ,Call/WhatsApp: : +2348071622464 , his website: https://urgentspell.blogspot.com .

    ReplyDelete
  11. I want to use this opportunity I have to say a big thanks to Dr Great for getting back my ex husband. I'm Linda Gibson from USA, after 7 years of marriage my husband left me for another woman I did whatever I could to get him back but all I did was in vain I was sad, but I didn't lose hope of getting him back because I had faith in God. So I search online on how to get my husband back, and I came across a post of Dr Great of how he helped a lady to get back her ex I felt I should give him a try, I contacted him and told him the pain I was going through, he told me what to do and I did it then he casted a love spell for me 48 hours later my husband called me and told me he is sorry for what he did and that he misses me very much later that day he came back home and he hugged me and that how our relationship became stronger. For the marvelous things Dr Great has done for me it will be unfair for me no to let the whole world know that such a powerful spell caster do live. If you want to get back your ex fast email Dr Great at infinitylovespell@gmail.com

    ReplyDelete
  12. Urgent effective love Spell caster to help you bring back ex lover & save you marriage fast Unityspelltemple@gmail.com is certainly the best spell caster online and his result is 100% guarantee!.
    My Name Olivia Stephen form Tx,USA. 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 (Urgent effective 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 ,or Call/WhatsApp him on:+2348071622464 ,his website:https://urgenteffectivespell.blogspot.com.

    ReplyDelete
  13. Welcome to Peter__spell official page of wonder. I cast all dark spell on riches,love portion or love spell,marriage spell, good job, appointment,good luck spell, dating, healing of sickness instantly or disease, success spell, protective spell and any spell of your choice. Contact me WhatsApp +2348073141298 to get help with anything you want.contact me today and make things better Email: peterlovespell1@gmail.com

    ReplyDelete
  14. I am, Susan Wanda from USA, North Carolina I promise to share this testimony all over the world once my Husband return back to me, and today with all due respect I want to thank dr. Odenore for bringing joy and happiness to my relationship and my family. I want to inform you all that there is a spell caster that is real and genuine. I never believed in any of these things until i loosed my husband, I required help until i found a great spell caster, And he cast a love spell for me, and he assured me that I will get my husband back in two days after the spell has been cast. Three days later, my phone rang, and so shockingly, it was my husband who has not called me for past 6 months now, and made an apology for the heart break, and told me that he is ready to be my back bone till the rest of his life with me. Dr Odenore, released him up to know how much I loved and wanted him. And opened his eyes to picture how much we have share together. As I`m writing this testimony right now I`m the most happiest girl on earth and me and my husband is living a happy life and our love is now stronger than how it were even before our break up. So that`s why I promised to share my testimony all over the universe. All thanks goes to Dr Odenore for the excessive work that he has done for me. Below is the email address in any situation you are undergoing a heart break, and I assure you that as he has done mine for me, he will definitely help you too. contact him now on email odenoretemple@gmail.com

    (1) Cancer spell
    (2) Pregnancy spell
    (3) Hiv/aids spell*
    (4) Getting your scam money back*
    (5) If you want a child.
    (6) if you always have bad dream
    (7) Spell to Get your love one out of jail .
    (8) Get a huge loan without paying any fee spell*
    (9) You want women/men to run after you.
    (10) If you want your ex back.
    Contact him today for your help and you will be happy for ever. REPLY (email : odenoretemple@gmail.com ) WhatsApp him +2349068901741

    ReplyDelete
  15. Online Solution To Love Problem ( He Is Expert Astrologer In This ) +91 8764361313
    Girlfriend Problem Solution
    Love Problem Solution

    ReplyDelete
  16. Online Solution To Love Problem ( He Is Expert Astrologer In This ) +91 8764361313
    Girlfriend Problem Solution
    Love Problem Solution
    Love Marriage Solution

    ReplyDelete
  17. Real And Urgent Spell Caster Reviews To Solve Your Relationship Problem Dr Davi..

    I am from Canada, I have great joy in me as i am writing this testimony about the great man called Dr. Davi When my lover left me i never taught that i will be able to get her back after all she put me through, But i am so happy that after the interference of Dr. Davi i was able to get my lover back within 48hours. Are you going through a break-up or divorce? Do you need your Ex back fast? Don't cry anymore, contact Dr Davi powerful Love spell that work fast now!! I was hurt and heart broken when my lover breakup with me, and i could not know what next to do again, I love my girlfriend so much but she was cheating on me with another man and this makes her break up with me so that she can be able to get married to the other man and this guy use witchcraft on my girlfriend to make her hate me and our kids and this was so critical and uncalled-for. I went to Florida to see a friend and who was having the same problem with me but she later got her husband back with the Same Dr. Davi love spell. She told me that Dr Davi help with love spell in getting back lost lover back, and i decided to contact the same Dr Davi and he told me what is needed to be done for me to have my woman back. To my surprise my lover really called me and told me that she miss me so much, Oh My God! i was so excited, and today i am happy with my woman again and we are joyfully living together as one big family and i thank the powerful spell caster Dr Davi for bringing back my lover and i decided to share my story on the internet that Dr Davi is the best spell caster online who i will always pray to live long to help his children in the time of trouble, If you have any problem contact Dr Davi and i guarantee you that he will help you,Email him at:

    Email: Spelltemple@fastmail.com
    Call him: +55 (11) 97732-4658   

    ReplyDelete
  18. Real And Urgent Spell Caster Reviews To Solve Your Relationship Problem Dr Davi..

    I am from Canada, I have great joy in me as i am writing this testimony about the great man called Dr. Davi When my lover left me i never taught that i will be able to get her back after all she put me through, But i am so happy that after the interference of Dr. Davi i was able to get my lover back within 48hours. Are you going through a break-up or divorce? Do you need your Ex back fast? Don't cry anymore, contact Dr Davi powerful Love spell that work fast now!! I was hurt and heart broken when my lover breakup with me, and i could not know what next to do again, I love my girlfriend so much but she was cheating on me with another man and this makes her break up with me so that she can be able to get married to the other man and this guy use witchcraft on my girlfriend to make her hate me and our kids and this was so critical and uncalled-for. I went to Florida to see a friend and who was having the same problem with me but she later got her husband back with the Same Dr. Davi love spell. She told me that Dr Davi help with love spell in getting back lost lover back, and i decided to contact the same Dr Davi and he told me what is needed to be done for me to have my woman back. To my surprise my lover really called me and told me that she miss me so much, Oh My God! i was so excited, and today i am happy with my woman again and we are joyfully living together as one big family and i thank the powerful spell caster Dr Davi for bringing back my lover and i decided to share my story on the internet that Dr Davi is the best spell caster online who i will always pray to live long to help his children in the time of trouble, If you have any problem contact Dr Davi and i guarantee you that he will help you,Email him at:

    Email: Spelltemple@fastmail.com
    Call him: +55 (11) 97732-4658   

    ReplyDelete