从 Java 中的字符串列表中查找每个短语出现的最佳方法 [英] Optimal approach to find occurrences of each phrase from a list in a string in Java
本文介绍了从 Java 中的字符串列表中查找每个短语出现的最佳方法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我对此进行了大量搜索，大多数帖子都在谈论在 2 个数组列表之间找到公共字符串，这可以使用 Collections.retainAll 或包含与文本进行比较的单个单词的 ArrayList 来完成.
I searched quite a bit on this and most posts are talking either about finding common strings between 2 arraylists which can be done with Collections.retainAll or an ArrayList containing individual words compared against text.
我的文本在 Java 中可能看起来像这样.
I have text which may look something like this in Java.
String text = "Get a placement right today by applying to our interviews and don't forget to email us your resume. This is a top job opportunity to get yourself acquainted with real world programming and skill building. Hurry! apply for placement now here";
我有一个 ArrayList，它有 2 个字符串，安置"和工作机会"
I have an ArrayList that has lets say 2 strings, "placement" and "job opportunity"
我希望结果是安置(2)和工作机会(1)我目前想到了几种方法，但我想知道实现这一目标的最佳方法.
I would like the results as placement(2) and job opportunity(1) There are several approaches I have in mind currently but I would like to know the optimal way for achieving this.
方法一为 ArrayList 中的每个单词维护一个计数器.对于 ArrayList 中的每个单词，执行一个 text.contains(word)，如果为真，则增加相应的计数器，如果文本中的单词多于 ArrayList 或 ArrayList 中的单词多于此处的文本，会发生什么?有没有最佳或更短的方法来实现相同的目标?我的 ArrayList 中可能有单词或短语.提前感谢您的建议.
Approach 1 Maintain a counter for each word in the ArrayList. For each word in the ArrayList, execute a text.contains(word) and if its true, increment the corresponding counter, What happens if there are more words in the text than the ArrayList or more words in the ArrayList than the text here? Is there any optimal or shorter way to achieve the same? I may have words or phrases in my ArrayList. Thanks for your suggestions in advance.
推荐答案
如果我理解正确，这个问题是模式匹配问题的一个实例.此维基百科页面列出了最佳字符串搜索算法及其平均和最坏情况的复杂度.如果我没记错的话，Alfred V. Aho、Jerffery Ullman 和 John E. Hopcroft 对算法的设计和分析对 模式匹配章节中的基于有限状态自动机的搜索.
If I understand correctly this problem is an instance of pattern matching problem. This wikipedia page lists the optimal string searching algorithms along with their average and worst case complexities. If I remember correctly Design and analysis of algorithms by Alfred V. Aho, Jerffery Ullman and John E. Hopcroft has a analysis of the Finite-state automaton based search in the pattern matching chapter.
以下两个似乎最有效.
我在 http://algs4.cs.princeton.edu我也会在这里复制这些文件，以防链接失效.实现:
I found the implementation of both of the algorithms on http://algs4.cs.princeton.edu I'll copy the files here too in case links go down. Implementations:
- KMP 实现(时间复杂度 Θ(m) + Θ(n))
- Boyer Moore 实现(时间复杂度 Θ(m + k)+ O(n))
- KMP implementation (Time Complexity Θ(m) + Θ(n))
- Boyer Moore implementation (Time Complexity Θ(m + k) + O(n))
StdOut 就是 System.out
StdOut is simply System.out
备份 KMP:
/******************************************************************************
* Compilation: javac KMP.java
* Execution: java KMP pattern text
* Dependencies: StdOut.java
*
* Reads in two strings, the pattern and the input text, and
* searches for the pattern in the input text using the
* KMP algorithm.
*
* % java KMP abracadabra abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: abracadabra
*
* % java KMP rab abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: rab
*
* % java KMP bcara abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: bcara
*
* % java KMP rabrabracad abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: rabrabracad
*
* % java KMP abacad abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: abacad
*
******************************************************************************/
/**
* The <tt>KMP</tt> class finds the first occurrence of a pattern string
* in a text string.
* <p>
* This implementation uses a version of the Knuth-Morris-Pratt substring search
* algorithm. The version takes time as space proportional to
* <em>N</em> + <em>M R</em> in the worst case, where <em>N</em> is the length
* of the text string, <em>M</em> is the length of the pattern, and <em>R</em>
* is the alphabet size.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/53substring">Section 5.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*/
public class KMP {
private final int R; // the radix
private int[][] dfa; // the KMP automoton
private char[] pattern; // either the character array for the pattern
private String pat; // or the pattern string
/**
* Preprocesses the pattern string.
*
* @param pat the pattern string
*/
public KMP(String pat) {
this.R = 256;
this.pat = pat;
// build DFA from pattern
int M = pat.length();
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X]; // Copy mismatch cases.
dfa[pat.charAt(j)][j] = j+1; // Set match case.
X = dfa[pat.charAt(j)][X]; // Update restart state.
}
}
/**
* Preprocesses the pattern string.
*
* @param pattern the pattern string
* @param R the alphabet size
*/
public KMP(char[] pattern, int R) {
this.R = R;
this.pattern = new char[pattern.length];
for (int j = 0; j < pattern.length; j++)
this.pattern[j] = pattern[j];
// build DFA from pattern
int M = pattern.length;
dfa = new int[R][M];
dfa[pattern[0]][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X]; // Copy mismatch cases.
dfa[pattern[j]][j] = j+1; // Set match case.
X = dfa[pattern[j]][X]; // Update restart state.
}
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param txt the text string
* @return the index of the first occurrence of the pattern string
* in the text string; N if no such match
*/
public int search(String txt) {
// simulate operation of DFA on text
int M = pat.length();
int N = txt.length();
int i, j;
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == M) return i - M; // found
return N; // not found
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param text the text string
* @return the index of the first occurrence of the pattern string
* in the text string; N if no such match
*/
public int search(char[] text) {
// simulate operation of DFA on text
int M = pattern.length;
int N = text.length;
int i, j;
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[text[i]][j];
}
if (j == M) return i - M; // found
return N; // not found
}
/**
* Takes a pattern string and an input string as command-line arguments;
* searches for the pattern string in the text string; and prints
* the first occurrence of the pattern string in the text string.
*/
public static void main(String[] args) {
String pat = args[0];
String txt = args[1];
char[] pattern = pat.toCharArray();
char[] text = txt.toCharArray();
KMP kmp1 = new KMP(pat);
int offset1 = kmp1.search(txt);
KMP kmp2 = new KMP(pattern, 256);
int offset2 = kmp2.search(text);
// print results
StdOut.println("text: " + txt);
StdOut.print("pattern: ");
for (int i = 0; i < offset1; i++)
StdOut.print(" ");
StdOut.println(pat);
StdOut.print("pattern: ");
for (int i = 0; i < offset2; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
后备博耶摩尔:
BoyerMoore.java
Below is the syntax highlighted version of BoyerMoore.java from §5.3 Substring Search.
/******************************************************************************
* Compilation: javac BoyerMoore.java
* Execution: java BoyerMoore pattern text
* Dependencies: StdOut.java
*
* Reads in two strings, the pattern and the input text, and
* searches for the pattern in the input text using the
* bad-character rule part of the Boyer-Moore algorithm.
* (does not implement the strong good suffix rule)
*
* % java BoyerMoore abracadabra abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: abracadabra
*
* % java BoyerMoore rab abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: rab
*
* % java BoyerMoore bcara abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: bcara
*
* % java BoyerMoore rabrabracad abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: rabrabracad
*
* % java BoyerMoore abacad abacadabrabracabracadabrabrabracad
* text: abacadabrabracabracadabrabrabracad
* pattern: abacad
*
******************************************************************************/
/**
* The <tt>BoyerMoore</tt> class finds the first occurrence of a pattern string
* in a text string.
* <p>
* This implementation uses the Boyer-Moore algorithm (with the bad-character
* rule, but not the strong good suffix rule).
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/53substring">Section 5.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*/
public class BoyerMoore {
private final int R; // the radix
private int[] right; // the bad-character skip array
private char[] pattern; // store the pattern as a character array
private String pat; // or as a string
/**
* Preprocesses the pattern string.
*
* @param pat the pattern string
*/
public BoyerMoore(String pat) {
this.R = 256;
this.pat = pat;
// position of rightmost occurrence of c in the pattern
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < pat.length(); j++)
right[pat.charAt(j)] = j;
}
/**
* Preprocesses the pattern string.
*
* @param pattern the pattern string
* @param R the alphabet size
*/
public BoyerMoore(char[] pattern, int R) {
this.R = R;
this.pattern = new char[pattern.length];
for (int j = 0; j < pattern.length; j++)
this.pattern[j] = pattern[j];
// position of rightmost occurrence of c in the pattern
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < pattern.length; j++)
right[pattern[j]] = j;
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param txt the text string
* @return the index of the first occurrence of the pattern string
* in the text string; N if no such match
*/
public int search(String txt) {
int M = pat.length();
int N = txt.length();
int skip;
for (int i = 0; i <= N - M; i += skip) {
skip = 0;
for (int j = M-1; j >= 0; j--) {
if (pat.charAt(j) != txt.charAt(i+j)) {
skip = Math.max(1, j - right[txt.charAt(i+j)]);
break;
}
}
if (skip == 0) return i; // found
}
return N; // not found
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param text the text string
* @return the index of the first occurrence of the pattern string
* in the text string; N if no such match
*/
public int search(char[] text) {
int M = pattern.length;
int N = text.length;
int skip;
for (int i = 0; i <= N - M; i += skip) {
skip = 0;
for (int j = M-1; j >= 0; j--) {
if (pattern[j] != text[i+j]) {
skip = Math.max(1, j - right[text[i+j]]);
break;
}
}
if (skip == 0) return i; // found
}
return N; // not found
}
/**
* Takes a pattern string and an input string as command-line arguments;
* searches for the pattern string in the text string; and prints
* the first occurrence of the pattern string in the text string.
*/
public static void main(String[] args) {
String pat = args[0];
String txt = args[1];
char[] pattern = pat.toCharArray();
char[] text = txt.toCharArray();
BoyerMoore boyermoore1 = new BoyerMoore(pat);
BoyerMoore boyermoore2 = new BoyerMoore(pattern, 256);
int offset1 = boyermoore1.search(txt);
int offset2 = boyermoore2.search(text);
// print results
StdOut.println("text: " + txt);
StdOut.print("pattern: ");
for (int i = 0; i < offset1; i++)
StdOut.print(" ");
StdOut.println(pat);
StdOut.print("pattern: ");
for (int i = 0; i < offset2; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
Copyright © 2002–2015, Robert Sedgewick and Kevin Wayne.
Last updated: Sat Aug 29 11:16:30 EDT 2015.
这篇关于从 Java 中的字符串列表中查找每个短语出现的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
