boyer expression

[shana07]

Kindly please someone who knows about this below expression share some info with me..

(x2 = x1 + s) & ( y2 = y1) & (f (x1, y1) > -1) => f(x1, y1) = f(x2, y2)[/i]

What does the relation mean? Are the left expr and right equal?
Thank you in advance..

[JosAH]

Kindly please someone who knows about this below expression share some info with me..

(x2 = x1 + s) & ( y2 = y1) & (f (x1, y1) > -1) => f(x1, y1) = f(x2, y2)[/i]

What does the relation mean? Are the left expr and right equal?
Thank you in advance..

It's just a conditional relation: A => B reads as "if A is true then B is true".
In your example A is "(x2 = x1+s) & (y2 = y1) & f(x1, y1) > -1)" which
reads as three and clauses: "a and b and c". Similar reasoning applies
the the expression B at the right side of the arrow.

The entire expression depends on the value of 's' and the definition of the
function 'f' of course. Without know those definitions the entire relation is
meaningless.

kind regards,

Jos

[shana07]

It's just a conditional relation: A => B reads as "if A is true then B is true".
In your example A is "(x2 = x1+s) & (y2 = y1) & f(x1, y1) > -1)" which
reads as three and clauses: "a and b and c". Similar reasoning applies
the the expression B at the right side of the arrow.

The entire expression depends on the value of 's' and the definition of the
function 'f' of course. Without know those definitions the entire relation is
meaningless.
kind regards,

Jos

Thank you very much Jos...first time look at the expr I was really clueless.
When you put 'if A is true then B is true' it's really simple to understand.
So, 'f' here could be any calculation functions such as division (/) or string search algorithm - boyer?

One last expr need to consult you...

(x3 = x1 + x2) & (y1 = y2 = y3) & (f (x,1, y1) = -1) => f(x3, y3) <= f(x2,y2) +len(x1)

From my understanding, the relation shows relation with lenght of string x1.
Any other means .....? Thank you again...

[JosAH]

Thank you very much Jos...first time look at the expr I was really clueless.
When you put 'if A is true then B is true' it's really simple to understand.
So, 'f' here could be any calculation functions such as division (/) or string search algorithm - boyer?

One last expr need to consult you...

(x3 = x1 + x2) & (y1 = y2 = y3) & (f (x,1, y1) = -1) => f(x3, y3) <= f(x2,y2) +len(x1)

From my understanding, the relation shows relation with lenght of string x1.
Any other means .....? Thank you again...

What article are you reading? I'm sure that there's some explaining text around
those darn formulas. My guess is that indeed x1, x2, x3 and y1, y2 and y3
are strings, '+' is the string concatenation operator and I think (just a guess) that
'f' is the failure function used in the Boyer Moore string matching algorithm.

kind regards,

Jos

[shana07]

What article are you reading? I'm sure that there's some explaining text around
those darn formulas. My guess is that indeed x1, x2, x3 and y1, y2 and y3
are strings, '+' is the string concatenation operator and I think (just a guess) that
'f' is the failure function used in the Boyer Moore string matching algorithm.

kind regards,

Jos

Brilliant guess.. Yes, I am reading Boyer Program article. Since you've mentioned about Boyer Moore algorithm..kindly please take a look at this below code ...(it's an open source)
How to get it started...please advise me Jos. Thanks

public static void main( String[] args)
      {
      if ( DEBUGGING )
         {
         System.out.println(Boyer.indexOf("dogcatwombat","cat"));
         System.out.println("dogcatwombat".indexOf("cat"));
 
         System.out.println(Boyer.indexOf("crtcamccmcarogcatwombat","cat"));
         System.out.println("crtcamccmcarogcatwombat".indexOf("cat"));
 
         System.out.println(Boyer.indexOf("dogcatwombat",""));
         System.out.println("dogcatwombat".indexOf(""));
 
         System.out.println(Boyer.indexOf("",""));
         System.out.println("".indexOf(""));
 
         System.out.println(Boyer.indexOf("","abcde"));
         System.out.println("".indexOf("abcde"));
 
         System.out.println(Boyer.indexOf("dogcatwombat","cow"));
         System.out.println("dogcatwombat".indexOf("cow"));
 
         String s = "create table foo (created_date datetime default sysdate not null)";
         System.out.println(s.indexOf("create", 10));
         System.out.println(Boyer.indexOf(s, "create", 10));
 
         try
            {
 
            // O P E N
            // Any file of sample characters
            File f = new File ("C:/temp/temp.txt");
            int size = (int) f.length();
            FileReader fr;
            fr = new FileReader(f);
 
            // R E A D
            char[] ca = new char[size];
            int charsRead = fr.read(ca);
            s = new String(ca);
 
            long start;
            long stop;
            int result = 0;
 
            start = System.currentTimeMillis();
            for ( int i=0; i<1000; i++ )
               {
               // Need to make different so optimiser will actually do
               // the work repeatedly.
               // search for strings like "efficiency9" that probably won't be there.
               result = Boyer.indexOf(ca,"efficiency"+i%10);
               }
            System.out.println("Boyer.indexOf(char[]): " + result);
            stop = System.currentTimeMillis();
            System.out.println("Elapsed:"
                               + (stop-start));
 
            // benchmark Boyer.indexOf
            start = System.currentTimeMillis();
            for ( int i=0; i<1000; i++ )
               {
               // Need to make different so optimiser will actually do
               // the work repeatedly.
               result = Boyer.indexOf(s,"efficiency"+i%10);
               }
            System.out.println("Boyer.indexOf(String): " + result);
            stop = System.currentTimeMillis();
            System.out.println("Elapsed:"
                               + (stop-start));
 
            // Benchmark String.indexOf
            start = System.currentTimeMillis();
            for ( int i=0; i<1000; i++ )
               {
               result = s.indexOf("efficiency"+i%10);
               }
            System.out.println("String.indexOf: " + result);
            stop = System.currentTimeMillis();
            System.out.println("Elapsed:"
                               + (stop-start));
 
            // C L O S E
            fr.close();
 
            }
         catch ( IOException e )
            {
            return;
            }
 
         } // end if debugging
      } // end main
   } // end class Boyer

[JosAH]

Brilliant guess.. Yes, I am reading Boyer Program article. Since you've mentioned about Boyer Moore algorithm..kindly please take a look at this below code ...(it's an open source)
How to get it started...please advise me Jos. Thanks

That is the last part of a Boyer class and it seems to exercise the algorithm a
bit by timing its performance. The entire test suite is not compiled if a boolean
DEBUGGING variable has not been set to true.

Don't try to scrape pieces of code from the internet; better read those articles
first until you understand the theory behind it all. To me it seems that you
also have to read up on the Java language itself too (no insult intended).

kind regards,

Jos

[shana07]

That is the last part of a Boyer class and it seems to exercise the algorithm a
bit by timing its performance. The entire test suite is not compiled if a boolean
DEBUGGING variable has not been set to true.

Don't try to scrape pieces of code from the internet; better read those articles
first until you understand the theory behind it all. To me it seems that you
also have to read up on the Java language itself too (no insult intended).

kind regards,

Jos

Thank you Jos..Really appreciate your effort to answer my Qs. Never mind..please don't give up to give any comment to me...as a java student I learn new thing everyday and I'm learning a lot about java from this forum...indeed.

[JosAH]

The Boyer-Moore algorithm is not a trivial algorithm, nor is the Knuth-Morris-Pratt
algorithm which is a variation on the same theme. Both are clever algorithms for
finding a substring somewhere in a string in O(n) where n is the length of the
string to be scanned. Can't you start with something simpler, easier to comprehend?

kind regards,

Jos

[shana07]

The Boyer-Moore algorithm is not a trivial algorithm, nor is the Knuth-Morris-Pratt
algorithm which is a variation on the same theme. Both are clever algorithms for
finding a substring somewhere in a string in O(n) where n is the length of the
string to be scanned. Can't you start with something simpler, easier to comprehend?

kind regards,

Jos

Jos, I shall try....
It's just happened that I need to study the Boyer program that is given to us..

[JosAH]

Jos, I shall try....
It's just happened that I need to study the Boyer program that is given to us..

Ah, ok, if it's a "given thing" I suppose you do have to study it. Try to understand
that failure function first then. Don't think about coding anything yet. Those
pattern matching algorithms have two phases:

1) construct the failure function given a pattern.
2) match a string for a pattern using that failure function.

A failure function is just an aray containing index values; the length of the array
is as long as the pattern to be found and every entry in that array tells what
part of the pattern has been matched if the current character in the pattern didn't
match against a character in the string.

kind regards,

Jos

[shana07]

Ah, ok, if it's a "given thing" I suppose you do have to study it. Try to understand
that failure function first then. Don't think about coding anything yet. Those
pattern matching algorithms have two phases:

1) construct the failure function given a pattern.
2) match a string for a pattern using that failure function.

A failure function is just an aray containing index values; the length of the array
is as long as the pattern to be found and every entry in that array tells what
part of the pattern has been matched if the current character in the pattern didn't
match against a character in the string.

kind regards,

Jos

You mean this function?

  /**
  * Calculate how many chars you can skip
  * to the right if you find a mismatch.
  * It depends on what character is at
  * the end of the word when you find a mismatch.
  * We must match the pattern, char by char, right to left.
  * Only called after degenerate cases,
  * (e.g. null, zero-length and 1-length Pattern) are eliminated.
  */
   private final void analysePattern ()
      {
      if ( pattern.equals(prevPattern) )
         {
         return;
         }
      // get pattern in fast-to-access charArray form
      patternArray = pattern.toCharArray();
      // Calculate how many slots we can skip to the right
      // depending on which char is at the end of the word
      // when we find a match.
      // Recycle old array if possible.
      if ( skip == null ) skip = new int [256];
      for ( int i=0; i<256; i++ )
         {
         skip[i] = lenPat;
         } // end for
 
      for ( int i=0; i<lenPat-1; i++ )
         {
         // The following line is the key to the whole algorithm.
         // It also deals with repeating letters in the pattern.
         // It works conservatively, considering only the last
         // instance of repeating letter.
         // We exclude the last letter of the pattern, because we are
         // only concerned with what to do on a mismatch.
         skip[patternArray[i] & 0xff] = lenPat-i-1;
         } // end for
      prevPattern = pattern;
      } // end analysePattern

[JosAH]

You mean this function?

Yup, that function. It sets up the failure function.

kind regards,

Jos