Class BoyerMoore

java.lang.Object
AEDs3.PatternMatching.BoyerMoore
public class BoyerMoore extends Object
Implementa o algoritmo de Boyer-Moore para busca eficiente de padrões em textos. Este algoritmo é utilizado para encontrar a posição de um padrão dentro de um texto, utilizando uma técnica de pré-processamento para otimizar a busca.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int
    ALPHABET_SIZE
    Tamanho do alfabeto ASCII estendido.
    private int[]
    badCharTbl
    Tabela de caracteres ruins para desalinhamento.
    private byte[]
    pattern
    Padrão em bytes.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BoyerMoore(String patternText)
    Construtor da classe BoyerMoore que inicializa o padrão a ser buscado e preenche a tabela de caracteres ruins.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getPatternLength()
    Retorna o comprimento do padrão.
    static boolean
    match(String pattern, String text)
    Verifica se o padrão especificado está presente no texto fornecido.
    private void
    preprocess()
    Preprocessa o padrão preenchendo a tabela de caracteres ruins.
    int
    search(byte[] text, int start)
    Executa a busca do padrão no texto fornecido a partir de uma posição inicial.
    static List<Integer>
    searchInStream(InputStream in, String pattern, int blockSize)
    Busca todas as ocorrências do padrão em um fluxo de entrada, processando o texto em blocos.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • ALPHABET_SIZE

      private static final int ALPHABET_SIZE
      Tamanho do alfabeto ASCII estendido.
      See Also:

    • pattern

      private byte[] pattern
      Padrão em bytes.

    • badCharTbl

      private int[] badCharTbl
      Tabela de caracteres ruins para desalinhamento.

  • Constructor Details

    • BoyerMoore

      public BoyerMoore(String patternText)
      Construtor da classe BoyerMoore que inicializa o padrão a ser buscado e preenche a tabela de caracteres ruins.
      Parameters:
      patternText - O padrão de texto que será buscado.

  • Method Details

    • preprocess

      private void preprocess()
      Preprocessa o padrão preenchendo a tabela de caracteres ruins. Esta tabela é utilizada para determinar o deslocamento do padrão em caso de falha na correspondência durante a busca.

    • search

      public int search(byte[] text, int start)
      Executa a busca do padrão no texto fornecido a partir de uma posição inicial.
      Parameters:
      text - O vetor de bytes onde a busca será realizada.
      start - A posição inicial no vetor onde a busca deve começar.
      Returns:
      A posição onde o padrão foi encontrado ou -1 se não encontrado.

    • getPatternLength

      public int getPatternLength()
      Retorna o comprimento do padrão.
      Returns:
      O tamanho do padrão em bytes.

    • match

      public static boolean match(String pattern, String text) throws IOException
      Verifica se o padrão especificado está presente no texto fornecido.
      Parameters:
      pattern - O padrão a ser buscado.
      text - O texto onde a busca será realizada.
      Returns:
      true se o padrão for encontrado no texto, caso contrário, false.
      Throws:
      IOException - Se ocorrer um erro de leitura do texto.

    • searchInStream

      public static List<Integer> searchInStream(InputStream in, String pattern, int blockSize) throws IOException
      Busca todas as ocorrências do padrão em um fluxo de entrada, processando o texto em blocos.
      Parameters:
      in - O fluxo de entrada contendo o texto onde a busca será realizada.
      pattern - O padrão a ser buscado.
      blockSize - O tamanho dos blocos a serem lidos do fluxo de entrada.
      Returns:
      Uma lista de inteiros representando as posições onde o padrão foi encontrado.
      Throws:
      IOException - Se ocorrer um erro de leitura do fluxo de entrada.