最佳的方法来找到一个列表中的每个词的出现在Java中的字符串 [英] Optimal approach to find occurrences of each phrase from a list in a string in Java
本文介绍了最佳的方法来找到一个列表中的每个词的出现在Java中的字符串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我搜索这个最帖子相当多的谈论要么要找到2的ArrayList可与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.
方法1
维持ArrayList中每个单词的计数器。对于ArrayList中的每个单词，执行text.contains（字），如果其真正的，增加相应的计数器，会发生什么事，如果有文本比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.阿霍，乌尔曼Jerffery和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.
以下的2种似乎是最有效的。
Following two seem to be most efficient.
- KMP matching algorithm
- Boyer Moore string search algorithm
我发现两者的算法的实现上 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 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屋！
查看全文
