プログラミングの美しさ-最短要約の生成
3646 ワード
package structure;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
*
* : , M , , ; N ,
* String extractSummary(String description,String[] key words),
* N ( ) ,
* : w1,w2,q1,w3,w4,w5,q2,w6,w7,q1,w8,w9,w10 , q1,q2
* 1 , , , , ,
*/
public class ShortestSummary {
String[] text; // = "hello world tst sepring sun flower hello";
String[] keywords;// = { "hello", "world" };
Map<String, Integer> map = new HashMap<String, Integer>();
int[] count;
public ShortestSummary(String[] text, String[] keywords) {
this.text = text;
this.keywords = keywords;
count = new int[keywords.length];
for (int i = 0, len = keywords.length; i < len; i++)
map.put(keywords[i], i);
}
/**
* text[] , , , ,
* , : text[] = {a a a b c d a} key {b d }
* :( ){a a a b c d } 6
* ( ){a a b c d } 5
* ( ) {a b c d } 4
* ( ){b c d } 3
* ,
* , {a a a b c d},from ,to ,from-to , , from ,
* [from+1 ,to] [from,to] , , from ,[from+1,to] , to ,
* from,to ,
*/
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=*/
public void execute() {
int start = 0, len = text.length, min = len;
for (int i = 0; i < len; i++) {
int t = exec(i, len - 1);
if (t > -1)
if (min > t) {
min = t;
start = i;
}
}
for (int i = start; i <= start + min; i++)
System.out.print(text[i] + " ");
}
private int exec(int from, int to) {
count = new int[keywords.length];
int start = from;
while (from <= to && !isAllgeted()) {
Integer i = map.get(text[from]);
if (i != null) {
count[i]++;
}
from++;
}
if (isAllgeted())
return from - start - 1;
return -1;
}
private boolean isAllgeted() {
for (int i = 0, len = count.length; i < len; i++)
if (count[i] == 0)
return false;
return true;
}
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=*/
// ,
void execute2(){
int start = 0,end=0,min = text.length,len = text.length,targetStart = 0,targetEnd = len;
while(true){
while(end<len && !isAllgeted()){
Integer t = map.get(text[end]);
if(t !=null)
count[t]++;
end++;
} // ,
while(isAllgeted() && start<=end){
if(end-start<min){
min = end-start;
targetStart = start;
targetEnd = end;
}
Integer t = map.get(text[start]);
if(t !=null)
count[t]--;
start ++ ;
}
if(end>=len)break;
}
for(int i=targetStart;i<targetEnd;i++)
System.out.print(text[i]+" ");
}
public static void main(String args[]) {
String[] text = "hello software hello test world spring sun flower hello".split(" ");
String[] keys = {"hello","world"};
ShortestSummary s = new ShortestSummary(text, keys);
s.execute2();
}
}