Java Program to Implement Bitap Algorithm

«
»
This is a Java Program to Implement Bitap Algorithm. The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is “approximately equal” to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.

Here is the source code of the Java Program to Implement Bitap Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to implement Bitap Algorithm
  3.  **/
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7. import java.io.IOException;
  8.  
  9. /** Class Bitap **/
  10. public class Bitap
  11. {
  12.     /** function findPattern **/
  13.     public void findPattern(String t, String p)
  14.     {
  15.         char[] text = t.toCharArray();
  16.         char[] pattern = p.toCharArray();
  17.         int pos = bitap_search(text, pattern);
  18.         if (pos == -1)
  19.             System.out.println("\nNo Match\n");
  20.         else
  21.             System.out.println("\nPattern found at position : "+ pos);
  22.     }
  23.     /** Bitap search **/
  24.     private int bitap_search(char[] text, char[] pattern)
  25.     {
  26.         int m = pattern.length;        
  27.         long pattern_mask[] = new long[Character.MAX_VALUE + 1];
  28.         /** Initialize the bit array R **/
  29.         long R = ~1;        
  30.         if (m == 0)
  31.             return -1;
  32.         if (m > 63)
  33.         {
  34.             System.out.println("Pattern is too long!");
  35.             return -1;
  36.         }
  37.         /** Initialize the pattern bitmasks **/
  38.         for (int i = 0; i <= Character.MAX_VALUE; ++i)
  39.             pattern_mask[i] = ~0;
  40.         for (int i = 0; i < m; ++i)
  41.                pattern_mask[pattern[i]] &= ~(1L << i);
  42.         for (int i = 0; i < text.length; ++i) 
  43.         {
  44.                /** Update the bit array **/
  45.             R |= pattern_mask[text[i]];
  46.             R <<= 1;     
  47.             if ((R & (1L << m)) == 0)
  48.                  return i - m + 1;
  49.         }
  50.         return -1;
  51.     }
  52.     /** Main Function **/
  53.     public static void main(String[] args) throws IOException
  54.     {    
  55.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  56.         System.out.println("Bitap Algorithm Test\n");
  57.         System.out.println("\nEnter Text\n");
  58.         String text = br.readLine();
  59.         System.out.println("\nEnter Pattern\n");
  60.         String pattern = br.readLine();
  61.         Bitap b = new Bitap(); 
  62.         b.findPattern(text, pattern);             
  63.     }
  64. }

Bitap Algorithm Test
 
 
Enter Text
 
bitapalgorithmtest
 
Enter Pattern
 
algorithm
 
Pattern found at position : 5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.