de.frame4j.text

Class RK

java.lang.Object

de.frame4j.text.CleverSSS

de.frame4j.text.RK

All Implemented Interfaces:

CharSequence, Comparable<CleverSSS>

@MinDoc(copyright="Copyright 2010  A. Weinert",
        author="Albrecht Weinert",
        version="V.39",
        lastModified="17.04.2021",
        usage="make for substrings to search for and use multiply",
        purpose="Rabin Karp substring search implementation")
public class RK
extends CleverSSS

Subsequence search — the immutable state.

An object of this class represents a character sequence to be searched for in (longer) character sequences in all variants of "indexOf". A RK object holds

• all immutable state
• plus some settings
• and methods
• implementing some search algorithms, in this class especially
  • Rabin Karp — hence the class name RK
  • and optimistic (O(n)) search guarded by a feasibility check.

The rationale behind Rabin Karp "indexOf" algorithms is their quite successful strive for O(n). The standard ("naive" loop-in-loop) algorithms, also used in String and consorts, are of type O(n*m).

Rabin Karp does not primarily compare character by character but two hash values. The hash of the smaller character sequence searched for is constant and stored finally in the RK object. The other hash is "sliding" over the longer character sequence to search in. The hash function used here is a polynomial with the character values acting as coefficients.

The rationale behind making objects of this class immutable respectively restricting the state to the constant parts of a concrete RK search is their multiple and threadsafe re-usability.

Motivation for clever subsequence searches and further background information see please in the abstract super class.


© Copyright 2009, 2010 Albrecht Weinert

Nested Class Summary

Nested classes/interfaces inherited from class de.frame4j.text.CleverSSS

CleverSSS.Simple

Field Summary

Fields

Modifier and Type	Field and Description
int	iFac The hash factor to remove the actual first character from a sliding hash.
char	subLast The sub sequence's last character.

Fields inherited from class de.frame4j.text.CleverSSS

algName, ignoreCase, ignoreWS, len, mskMod, optimisticOK, primF, subC

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	RK(char[] subC, char subLast, int subHash, int iFac, boolean ignoreCase, boolean ignoreWS, boolean optimisticOK) Constructor (for factory methods only, no checks).

Method Summary

Modifier and Type	Method and Description
static int	extHash(int oldHash, char charIn) Extend a RK hash by one character (helper function).
protected long	implAlgWhere(CharSequence sequ, int lk, int sI, int mxSi) The basic implementation of the RK search algorithm using this object's settings.
static CleverSSS	make(CharSequence sub, boolean ignoreCase) Make a RK for a subsequence to be searched for.
static CleverSSS	make(CharSequence sub, boolean ignoreCase, boolean ignoreWS) Make a RK for a subsequence to be searched for (later).
int	slideHash(int oldHash, char charOut, char charIn) Slide a hash for this RK hash by one character (helper function).

Methods inherited from class de.frame4j.text.CleverSSS

allWhere, asPair, asPairs, charAt, commonState, compareTo, endIndexOf, endIndexOf, equals, hashCode, implAlgWhere, indexOf, indexOf, lastIndexOf, lastIndexOf, lastWhereImpl, length, make, make, makeSimple, pair2long, state, subSequence, toCharA, toString, where, where, whereImpl

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.CharSequence

chars, codePoints

Field Detail

subLast

public final char subLast

The sub sequence's last character.

There is always at least one character, see CleverSSS.length().
In case of CleverSSS.ignoreCase this character is lower case.
In case of CleverSSS.ignoreWS this character is guaranteed to be > blank.

iFac

public final int iFac

The hash factor to remove the actual first character from a sliding hash.

Used in the Rabin Karp search algorithm.

Constructor Detail

RK

protected RK(char[] subC,
             char subLast,
             int subHash,
             int iFac,
             boolean ignoreCase,
             boolean ignoreWS,
             boolean optimisticOK)

Constructor (for factory methods only, no checks).

Method Detail

make

public static CleverSSS make(CharSequence sub,
                             boolean ignoreCase)

Make a RK for a subsequence to be searched for.

This method makes and returns a RK object for the sub sequence supplied. That object is suitable for subsequent multiple and multi-thread indexOf type searches for that sub sequence. If (all) that searches are to ignore case, this has to has to be (finally) set here.

For a null or empty sub null (no RK object) is returned, as this case requires no search at all.

make

public static CleverSSS make(CharSequence sub,
                             boolean ignoreCase,
                             boolean ignoreWS)

Make a RK for a subsequence to be searched for (later).

This method is equivalent to make(CharSequence, boolean) with the extra option to make the subsequence search totally white space ignoring if the the third parameter ignoreWS is supplied as true.

In that case only sub's non blank characters would be transferred to the RK object to be made.

Example: A search for "al L" in " H a l l o " both ignoring white space and case would yield 3 as the first matching index (and 8 as the first non matching index after the fitting sub sequence pattern).

extHash

public static int extHash(int oldHash,
                          char charIn)

Extend a RK hash by one character (helper function).

Hint: This (helper) method takes whatever value supplied for charIn. Ignoring case and or white space has to be done by the caller.

Parameters:

oldHash - the old hash value; supply 0 for new start

charIn - the character to put as new last character to the hash

Returns:

the updated hash value

slideHash

public final int slideHash(int oldHash,
                           char charOut,
                           char charIn)

Slide a hash for this RK hash by one character (helper function).

Hint: This (helper) method takes whatever value supplied for charIn and charOut. Ignoring case and or white space has to be done by the caller.

Parameters:

oldHash - the old hash value; supply 0 for new start

charIn - the character to put as new last character to the hash

charOut - the character to remove as old first character from the the sliding hash; supply 0 for new start or use extHash(1, charIn) to start

Returns:

the updated hash value

implAlgWhere

protected final long implAlgWhere(CharSequence sequ,
                                  int lk,
                                  int sI,
                                  int mxSi)

The basic implementation of the RK search algorithm using this object's settings.

This method is called by CleverSSS.whereImpl(CharSequence, int, int) for all non trivial cases and with checked / correct parameters.

Specified by:

implAlgWhere in class CleverSSS

Parameters:

sequ - the sequence to search in

lk - its correct or shortened) length

sI - the starting index for the search

mxSi - the maximum possible value of the match index

Returns:

first index and last index + 1 where sub was found in one long or -1 if no match

See Also:

CleverSSS.implAlgWhere()