Как использовать регулярное выражение для эффективного поиска назад?

Ответ 1

Механизм регулярного выражения Java не может искать назад. Фактически, единственный механизм регулярных выражений, который я знаю, который может это сделать, является единственным в .NET.

Вместо поиска в обратном направлении повторите все совпадения в цикле (поиск вперед). Помните об этом, если матч до позиции, которую вы хотите. Если совпадение находится после нужной позиции, выйдите из цикла. В псевдокоде (моя Java немного ржавая):

storedmatch = ""
while matcher.find {
  if matcher.end < offset {
    storedmatch = matcher.group()
  } else {
    return storedmatch
  }
}

Ответ 2

Следующий поиск класса назад и вперед (конечно).

Я использовал этот класс в приложении, где пользователи могут искать строки в длинном тексте (например, функция поиска в веб-браузере). Поэтому он проверен и хорошо работает для практических случаев использования.

Он использует подход, подобный тому, что описывает Ян Гойвартс. Он выбирает блок текста перед стартовой позицией и ищет его вперед, возвращая последнее совпадение, если оно есть. Если нет совпадения, если вы выбираете новый блок текста перед блоком и ищет его таким же образом.

Используйте его следующим образом:

Search s = new Search("Big long text here to be searched [...]");
s.setPattern("some regexp");

// search backwards or forward as many times as you like,
// the class keeps track where the last match was
MatchResult where = s.searchBackward();
where = s.searchBackward(); // next match
where = s.searchBackward(); // next match

//or search forward
where = s.searchForward();
where = s.searchForward();

И класс:

import java.util.regex.MatchResult;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/*
 * Search regular expressions or simple text forward and backward in a CharSequence
 *
 * 
 * To simulate the backward search (that Java class doesn't have) the input data
 * is divided into chunks and each chunk is searched from last to first until a 
 * match is found (inter-chunk matches are returned from last to first too).
 *
 * The search can fail if the pattern/match you look for is longer than the chunk
 * size, but you can set the chunk size to a sensible size depending on the specific
 * application.
 *
 * Also, because the match could span between two adjacent chunks, the chunks are
 * partially overlapping. Again, this overlapping size should be set to a sensible
 * size.
 *
 * A typical application where the user search for some words in a document will
 * work perfectly fine with default values. The matches are expected to be between
 * 10-15 chars, so any chunk size and overlapping size bigger than this expected 
 * length will be fine.
 *
 * */
public class Search {

    private int BACKWARD_BLOCK_SIZE = 200;
    private int BACKWARD_OVERLAPPING = 20;

    private Matcher myFwdMatcher;
    private Matcher myBkwMatcher;
    private String  mySearchPattern;
    private int myCurrOffset;
    private boolean myRegexp;
    private CharSequence mySearchData;

    public Search(CharSequence searchData) {
        mySearchData = searchData;
        mySearchPattern = "";
        myCurrOffset = 0;
        myRegexp = true;
        clear();
    }

    public void clear() {
        myFwdMatcher = null;
        myBkwMatcher = null;
    }

    public String getPattern() {
        return mySearchPattern;
    }

    public void setPattern(String toSearch) {
        if ( !mySearchPattern.equals(toSearch) ) {
            mySearchPattern = toSearch;
            clear();
        }
    }

    public CharSequence getText() {
        return mySearchData;
    }

    public void setText(CharSequence searchData) {
        mySearchData = searchData;
        clear();
    }

    public void setSearchOffset(int startOffset) {
        if (myCurrOffset != startOffset) {
            myCurrOffset = startOffset;
            clear();
        }
    }

    public boolean isRegexp() {
        return myRegexp;
    }

    public void setRegexp(boolean regexp) {
        if (myRegexp != regexp) {
            myRegexp = regexp;
            clear();
        }
    }

    public MatchResult searchForward() {

        if (mySearchData != null) {

            boolean found;

            if (myFwdMatcher == null)
            {
                // if it a new search, start from beginning
                String searchPattern = myRegexp ? mySearchPattern : Pattern.quote(mySearchPattern);
                myFwdMatcher = Pattern.compile(searchPattern, Pattern.CASE_INSENSITIVE).matcher(mySearchData);
                try {
                    found = myFwdMatcher.find(myCurrOffset);
                } catch (IndexOutOfBoundsException e) {
                    found = false;
                }
            }
            else
            {
                // continue searching
                found = myFwdMatcher.hitEnd() ? false : myFwdMatcher.find();
            }

            if (found) {
                MatchResult result = myFwdMatcher.toMatchResult();
                return onMatchResult(result);
            }
        }
        return onMatchResult(null);
    }

    public MatchResult searchBackward() {

        if (mySearchData != null) {

            myFwdMatcher = null;

            if (myBkwMatcher == null)
            {
                // if it a new search, create a new matcher
                String searchPattern = myRegexp ? mySearchPattern : Pattern.quote(mySearchPattern);
                myBkwMatcher = Pattern.compile(searchPattern, Pattern.CASE_INSENSITIVE).matcher(mySearchData);
            }

            MatchResult result = null;
            boolean startOfInput = false;
            int start = myCurrOffset;
            int end = start;

            while (result == null && !startOfInput)
            {
                start -= BACKWARD_BLOCK_SIZE;
                if (start < 0) {
                    start = 0;
                    startOfInput = true;
                }
                try {
                    myBkwMatcher.region(start, end);
                } catch (IndexOutOfBoundsException e) {
                    break;
                }
                while ( myBkwMatcher.find() ) {
                    result = myBkwMatcher.toMatchResult();
                }
                end = start + BACKWARD_OVERLAPPING; // depending on the size of the pattern this could not be enough
                                                    //but how can you know the size of a regexp match beforehand?
            }

            return onMatchResult(result);
        }
        return onMatchResult(null);
    }

    private MatchResult onMatchResult(MatchResult result) {
        if (result != null) {
            myCurrOffset = result.start();    
        }
        return result;
    }
}

И если вам нравится тестировать класс, вот пример использования:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;
import java.util.regex.MatchResult;
import javax.swing.text.DefaultHighlighter;
import javax.swing.text.BadLocationException;

public class SearchTest extends JPanel implements ActionListener {

    protected JScrollPane scrollPane;
    protected JTextArea textArea;
    protected boolean docChanged = true;
    protected Search searcher;

    public SearchTest() {
        super(new BorderLayout());

        searcher = new Search("");

        JButton backButton = new JButton("Search backward");
        JButton fwdButton  = new JButton("Search forward");

        JPanel buttonPanel = new JPanel(new BorderLayout());
        buttonPanel.add(fwdButton, BorderLayout.EAST);
        buttonPanel.add(backButton, BorderLayout.WEST); 

        textArea = new JTextArea("Big long text here to be searched...", 20, 40);
        textArea.setEditable(true);
        scrollPane = new JScrollPane(textArea);

        final JTextField textField = new JTextField(40);

        //Add Components to this panel.
        add(buttonPanel, BorderLayout.NORTH);
        add(scrollPane, BorderLayout.CENTER);
        add(textField, BorderLayout.SOUTH);

        //Add actions
        backButton.setActionCommand("back");
        fwdButton.setActionCommand("fwd");
        backButton.addActionListener(this);
        fwdButton.addActionListener(this);

        textField.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                final String pattern = textField.getText();
                searcher.setPattern(pattern);
            }
        } );

        textArea.getDocument().addDocumentListener( new DocumentListener() { 
            public void insertUpdate(DocumentEvent e) { docChanged = true; }
            public void removeUpdate(DocumentEvent e) { docChanged = true; }
            public void changedUpdate(DocumentEvent e) { docChanged = true; }
        });
    }

    public void actionPerformed(ActionEvent e)  {

        if ( docChanged ) {
            final String newDocument = textArea.getText();
            searcher.setText(newDocument);
            docChanged = false;
        }

        MatchResult where = null;

        if ("back".equals(e.getActionCommand())) {
            where = searcher.searchBackward();
        } else if ("fwd".equals(e.getActionCommand())) {
            where = searcher.searchForward();
        }

        textArea.getHighlighter().removeAllHighlights();

        if (where != null) {
            final int start = where.start();
            final int end   = where.end();
            // highligh result and scroll
            try {
            textArea.getHighlighter().addHighlight(start, end, new DefaultHighlighter.DefaultHighlightPainter(Color.yellow));
            } catch (BadLocationException excp) {}
            textArea.scrollRectToVisible(new Rectangle(0, 0, scrollPane.getViewport().getWidth(), scrollPane.getViewport().getHeight()));
            SwingUtilities.invokeLater(new Runnable() {
                    @Override
                    public void run() { textArea.setCaretPosition(start); }
            });
        } else if (where == null) {
            // no match, so let wrap around
            if ("back".equals(e.getActionCommand())) {
                searcher.setSearchOffset( searcher.getText().length() -1 );
            } else if ("fwd".equals(e.getActionCommand())) {
                searcher.setSearchOffset(0);
            }
        }
    }

    private static void createAndShowGUI() {
        //Create and set up the window.
        JFrame frame = new JFrame("SearchTest");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        //Add contents to the window.
        frame.add(new SearchTest());

        //Display the window.
        frame.pack();
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        //Schedule a job for the event dispatch thread:
        //creating and showing this application GUI.
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}

Ответ 3

Является ли строка поиска строго регулярным выражением (полный, насыщенный синтаксис?), потому что если нет, for(int j = line; j >= 0 ; j--), переверните строку, отмените совпадение и выполните поиск вперед;)

Ответ 4

Если предыдущий матч - это что-то, что вы уже согласовали в будущем, то как насчет создания списка совпадающих позиций при поиске вперёд, а затем просто использовать его для возврата назад вместо поиска назад?

Ответ 5

Я использую следующий простой класс для поиска назад в java

public class ReverseMatcher {
   private final Matcher _matcher;
   private final Stack<MatchResult> _results = new Stack<>();

   public ReverseMatcher(Matcher matcher){
       _matcher = matcher;
   }

   public boolean find(){
       return find(_matcher.regionEnd());
   }

   public boolean find(int start){
       if (_results.size() > 0){
           _results.pop();
           return _results.size() > 0;
       }
       boolean res = false;
       while (_matcher.find()){            
           if (_matcher.end() > start)
               break;
           res = true;
           _results.push(_matcher.toMatchResult());
       }
       return res;
   }

   public String group(int group){
       return _results.peek().group(group);               
   }

   public String group(){
       return _results.peek().group();               
   }

   public int start(){
       return _results.peek().start();
   }    

   public int end(){
       return _results.peek().end();
   }
}

с помощью:

String srcString = "1 2 3 4 5 6 7 8 9";
String pattern = "\\b[0-9]*\\b";
Pattern p = Pattern.compile(pattern);
Matcher m = p.matcher(srcString);
ReverseMatcher rm = new ReverseMatcher(m);
while (rm.find())
   System.out.print(rm.group() + " ");

: 9 8 7 6 5 4 3 2 1

или

while (rm.find(9))
   System.out.print(rm.group() + " ");

вывод: 5 4 3 2 1