1
\$\begingroup\$

I have invented the fastest string search algorithm. Can someone prove that it is not fastest?

I am not considering worst case scenarios.

The algorithm can be found here: https://sourceforge.net/projects/fastest-string-search-algo/files/


    /*
     * Choudhary algorithm
     */
    public static int choudharyStringSearchAlgorithm(char[] text, char[] pattern) {

        int i = 0;
        int index = 0;
        int end_index = 0;
        boolean not_found = false;

        int text_len = text.length;
        int pattern_len = pattern.length;

        int pi_44 = pattern_len - 1;
        int pi_34 = (3 * pattern_len) / 4;
        int pi_24 = pattern_len / 2;
        int pi_14 = pattern_len / 4;

        int[] skip_table = new int[ASIZE];

        // preprocess pattern and fill skip_table
        for (i = 0; i < pattern_len; i++) {
            skip_table[pattern[i]] = pattern_len - 1 - i;
        }

        // now search
        for (i = 0; i < text_len; i++) {

            if ((text_len - i) < pattern_len) {
                return -1;
            }

            if (pattern[pi_44] != text[i + pi_44]) {
                if (skip_table[(int) (text[i + pi_44])] > 0) {
                    i = i + skip_table[(int) (text[i + pi_44])] - 1;
                }
                continue;
            }

            if (pattern[0] != text[i]) {
                continue;
            }

            if (pattern[pi_24] != text[i + pi_24]) {
                continue;
            }

            if (pattern[pi_34] != text[i + pi_34]) {
                continue;
            }

            if (pattern[pi_14] != text[i + pi_14]) {
                continue;
            }

            end_index = i + pi_44;
            not_found = false;

            for (index = i; index <= end_index; index++) {
                if (text[index] != pattern[index - i]) {
                    not_found = true;
                    break;
                }
            } // end of inner for loop

            if (not_found == false) { // match is found
                return i;
            }

        } // end of outer for loop

        return -1;

    } // end of choudharyStringSearchAlgorithm
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Looks like you've re-invented Boyer-Moore-Horspool string searching. At least in theory, Boyer-Moore string searching is a bit faster (but honestly, the difference is quite small). Even though it's been invented before, independently re-inventing BMH is no mean feat. \$\endgroup\$ Jul 17 at 7:30
  • \$\begingroup\$ This algorithm is not Boyer-Moore-Horspool. Please see the algorithm carefully. It compares characters at indices pattern_len - 1, 0, (3 * pattern_len) / 4, pattern_len / 2, and pattern_len / 4 before going for full pattern search. \$\endgroup\$
    – Amit
    Jul 17 at 9:23
0
\$\begingroup\$

If you are searching for long patterns, your algorithm wins most of the time (long strings as far to the end of the text as possible are favored), but if you compare the algorithms on patterns up to 100 characters long (human search), Boyer-Moore smokes everyone and it is not even close.

Edit: After some testing I have found out that your algorithm is worse on long patterns than if you just implemented the skip table.

Edit 2: Actually here is the implementation that is consistently faster than every other algorithm in your collection more than 95% of the time:

public class MyTextSearch implements TextSearch
{
    @Override
    public int search(
            char[] text,
            char[] pattern
    )
    {
        int[] skip_table = new int[256];
        int patternLength = pattern.length - 1;
        char lastPatternChar = pattern[patternLength];

        Arrays.fill(skip_table, patternLength);

        for (int i = 0; i < pattern.length; i++)
        {
            skip_table[pattern[i]] = patternLength - i - 1;
        }

        for (int i = 0; i < text.length; i++)
        {
            if (i + patternLength >= text.length)
            {
                return -1;
            }

            char lastTextChar = text[i + patternLength];
            if (lastPatternChar != lastTextChar)
            {
                i += skip_table[lastTextChar];
                continue;
            }

            if (isEqual(text, i, pattern))
            {
                return i;
            }
        }

        return -1;
    }

    private boolean isEqual(
            char[] text,
            int at,
            char[] pattern
    )
    {
        for (int j = 0; j < pattern.length; j++)
        {
            if (text[at + j] != pattern[j])
            {
                return false;
            }
        }

        return true;
    }

    @Override
    public String name()
    {
        return "My Text Search";
    }
}

I have refactored your code a bit and it is on https://github.com/blazmrak/fastest-string-search if you are interested.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.