String Hashing

হ্যাশিং: হ্যাশিং একটা টেকনিক যার মাধ্যমে একটা কী(Key) ভ্যালুকে অন্য একটা ভ্যালুতে রূপান্তর করা যায়।
হ্যাশ ফাংশন: নতুন ভ্যালু বের করার যে গাণিতিক পদ্ধতি ব্যবহার করা হয় তাকে হ্যাশ ফাংশন বলে। হ্যাশ ফাংশন থেকে প্রাপ্ত ভ্যালুকে হ্যাশ ভ্যালু/হ্যাশ বলে। ভালো হ্যাশ ফাংশনে নিচের বৈশিষ্টগুলো থাকে-

• ধরি, \(X\) এবং \(Y\) দুইটি কী(Key) ভ্যালু এবং \(F()\) একটি হ্যাশ ফাংশন। এখন \(F(X)=F(Y)\) হবে যদি \(X=Y\) হয় এবং \(X\neq Y\) হলে \(F(X)\neq F(Y)\) হবে।
• ব্যবহারিক অর্থে হ্যাশ ভ্যালুর সাইজ যথেষ্ট ছোট হতে হবে।
• হ্যাশ ফাংশন সহজ ও সরল হতে হবে যাতে সহজে হ্যাশ ভ্যালু বের করা যায়।
• হ্যাশ ফাংশন এমন হতে হবে যাতে কলিশন(Collision) হওয়ার সম্ভাবনা কম থাকে।
• একমুখী হ্যাশিং ব্যবহার করতে হবে যাতে নতুন হ্যাশ ভ্যালু থেকে কী(Key) ভ্যালুতে রূপান্তর না করা যায়।

কলিশন: দুইটি ভিন্ন কী(Key) এর জন্য যদি একই হ্যাশ ভ্যালু বের হয়।

ধরি, আমরা এখন একটি স্ট্রিং \(S=``ADC"\) এর জন্য হ্যাশ ভ্যালু বের করবো। যেখানে হ্যাশ ফাংশন- \[F(S)= \sum_{i=1}^{N} X_i\] এখানে \(X_i= i\)th অ্যালফাবেটের পজিশন এবং অ্যালফাবেট \(A,B,C,...,Z\) এর পজিশন যথাক্রমে \(1,2,3,...,26\)।
\[\therefore F(S) = 1 + 4 + 3 = 8\] এখন বলতে হবে এই হ্যাশ ফাংশনটি কি ভালো? একটু চিন্তা করলেই বলা যাচ্ছে যে এই হ্যাশ ফাংশনটি ভালো না। কারণ এর কলিশন হওয়ার সম্ভাবনা অনেক বেশি। উক্ত হ্যাশ ফাংশনটি \(``ADC"\) এবং \(``ACD"\) এর জন্য একই হ্যাশ ভ্যালু দিবে।

অনেক পদ্ধতির হ্যাশ ফাংশন হতে পারে। আমরা নিচে একটি পদ্ধতি নিয়ে কাজ করবো। পদ্ধতিটি হচ্ছে-
ধরি, \(N\) সাইজের একটি স্ট্রিং \(S = S_1 S_2 ... S_N\) দেওয়া আছে। এখন হ্যাশ ফাংশন-
\[ F(S) = \sum_{i=1}^{N} X_i.P^{N-i}\] এখানে \(X_i= i\)th অ্যালফাবেটের পজিশন এবং \(P=\) বেস ভ্যালু (সাধারণত ব্যবহারিত অ্যালফাবেট সংখ্যার চাইতে বড় একটা প্রাইম নাম্বার নেওয়া হয়)। ধরি, \(P=27\), তাহলে \(F(``ADC") = 840\) এবং \(F(``ACD") = 814\).
কিন্তু এখন প্রব্লেম হচ্ছে যদি স্ট্রিং এর সাইজ অনেক বড় হয় তবে হ্যাশ ভ্যালুও অনেক বড় হয়ে যাবে। ভালো হ্যাশ ফাংশন বানানোর জন্য হ্যাশ ভ্যালু বড় হতে দেওয়া যাবে না। তাই এই প্রব্লেম এর সমাধান হিসেবে আমরা একটা কাজ করতে পারি...হ্যাশ ভ্যালুকে একটা নাম্বার দিয়ে মড করতে পারি। এখন যেকোনো নাম্বার দিয়ে মড করাটা কি Feasible?!
উত্তরটি হচ্ছে 'না'। তাহলে নাম্বারটি কেমন নিবো? এর উত্তর হচ্ছে একটা বড় প্রাইম নাম্বার নিবো। প্রাইম নাম্বার কেন নিবো? Modular Arithmetic নিয়ে আইডিয়া থাকলে এটা খুব সহজেই বুঝা যাবে। আর প্রাইমটা বড় কেন নিবো এবং কত বড় নিবো? - এই দুইটা প্রশ্নের উত্তর এখানে পাওয়া যাবে।
[To Be Continued...]

Hashing

Source :

Link1 Link2 Link3

Code :

Application :

1. Given a text and a pattern. Find all occurrences of the pattern.

:: Check all sub-strings of length |pattern| in text & compare hash value in O(|text| + |pattern|).

2. Given two string S1 & S2. Find longest common sub-string between them.

:: Binary search on length and check them with Hash value.

3. Find lexicographic minimal cyclic shift of a string of length n.

:: See this.

4. Given a string S. Find a smallest period in it.

 :: Let answer will be of length X and it will divide |S|. Then we will check Hash value of S[0...n-x-1] & S[x...n-1] are equal or not.

5. Given two trees. Check if they are isomorphic or not.

:: Read this.

6. Read this also.

Problem :

1. NHAY - A Needle in the Haystack

2. ADAPHOTO - Ada and Terramorphing (10^6 version)

3. 1517. Freedom of Choice (10^5 version)

4. Minimal Rotation

5.  C. Watto and Mechanism

6. D. Palindrome pairs

7. E. Games on a CD

*** Solve all problems mentioned in CP algo.