You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@uima.apache.org by tw...@apache.org on 2008/01/31 14:00:14 UTC
svn commit: r617123 [2/2] - in /incubator/uima/sandbox/trunk/Tagger: ./
desc/ models/ models/english/ models/german/
src/main/java/org/apache/uima/examples/tagger/
Added: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/ModelGenerationBytes.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/ModelGenerationBytes.java?rev=617123&view=auto
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/ModelGenerationBytes.java (added)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/ModelGenerationBytes.java Thu Jan 31 05:00:08 2008
@@ -0,0 +1,810 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+
+package org.apache.uima.examples.tagger;
+
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.io.ObjectOutputStream;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.Map.Entry;
+
+/**
+ * Trains an N-gram model for the tagger, iterating over the files from some predefined training directory
+ * Writes the resulting model to a binary fileSystem
+ *
+ *
+ * NB. At the moment- both bi-and trigram statistics are saved in one model file..
+ *
+ */
+
+
+public class ModelGenerationBytes implements java.io.Serializable{
+
+ private static final long serialVersionUID = 1L;
+
+ public Map posMap = new HashMap();
+ public Map suffix_tree= new HashMap ( ) ;
+
+ public Map suffix_tree_capitalized = new HashMap();
+ /**
+ * Map containing {@code <word,tag>} probabilities, that is probability of a certain word given a certain tag at a time t: P(word<sub>t</sub>|tag<sub>t</sub>))
+ *
+ */
+ public Map word_probs = new HashMap();
+
+ /**
+ * Map containing N-gram probabilities
+ */
+
+ public Map transition_probs = new HashMap() ;
+
+
+ transient List<String> posList = new ArrayList<String>();
+
+ int N; // for the N-gram model
+
+ double [] lambdas2 = new double[2];
+ double [] lambdas3 = new double[3];
+ public double theta; // for suffix probabiliites smoothing
+
+ // Word Counts...
+ Map<String, Integer> counts = new HashMap<String, Integer>();
+ transient String InputDir;
+ transient String OutputFile;
+ transient List corpus;
+
+ /**
+ * @param N N=1, 2 or 3
+ * @param InputDir input directory name
+ * @param OutputFile output file name
+ * MapBrownToPenn TagMapping
+ */
+ @SuppressWarnings("unchecked")
+public ModelGenerationBytes(List<Token> corpus, String OutputFile) {
+
+ this.OutputFile = OutputFile;
+ this.corpus = corpus;
+
+ }
+
+ /**
+ * Check is the token is capitalized
+ */
+ static boolean capitalized(String word){
+ boolean b;
+ char first_letter = word.charAt(0);
+ char capitalized = word.toUpperCase().charAt(0);
+ if (first_letter == capitalized) {
+ b = true;
+ } else {
+ b = false;
+ }
+ return b;
+ }
+
+
+ int tokens_count_all_corpus = 0;
+
+
+
+
+ /**
+ * Reads sentences, extracts {@code <word, possible parts-of-speech>} frequency patterns
+ * @param corpus list containing all tokens of the training corpus of the type {@link Token}}
+ * @return map containing frequency counts for {@code <word, its pos>}
+ */
+ private Map<String,Map<Byte, Double>> get_lexicon(List<Token> corpus){
+
+ /*
+ * Extracts all available POS from the text and puts them into the map of POS - string and corresponding ID
+ */
+
+ for (int x=0; x<corpus.size(); x++){ // iterate over tokens with their corresponding POS
+
+ posList.add(corpus.get(x).pos); // Filling of POS tags list with available in the training corpus POSs.. (TODO: admissable POSs should probably be trasmitted with parameter file..to avoid noise)
+ }
+
+
+ posMap = getHashmap(posList);
+ System.out.println("Number of tags in the training corpus: "+posMap.size());
+
+ Map<String,Map<Byte, Double>> lexicon= new HashMap<String,Map<Byte, Double>>();
+
+ // Map<String, Integer> counts = new HashMap<String,Integer>();
+ for (int x=0; x<corpus.size(); x++){ // iterate over tokens with their corresponding POS
+
+ Map<Byte, Double> pos = new HashMap<Byte, Double>();
+ tokens_count_all_corpus +=1;
+ Token current_token = corpus.get(x);
+ // System.out.println(current_token.word);
+ // posList.add(current_token.pos); // Filling of POS tags list with available in the training corpus POSs.. (TODO: admissable POSs should probably be trasmitted with parameter file..to avoid noise)
+
+ /*
+ // a try to get a separate entry for numbers, decreased the accuracy, so discarded at the moment..
+ Pattern p = Pattern.compile("[0-9]*");
+ Matcher m = p.matcher(current_token.word);
+ boolean b = m.matches();
+ // if a current tokren is a number
+ if (b) {
+ System.out.println(current_token.word+" "+current_token.pos);
+ current_token.word = "@card";
+ }
+ */
+ if (lexicon.containsKey(current_token.word)){
+ // System.out.println(current_token.pos);
+
+ // if the token is already in a dictionary, then get its POS-s
+ // Map pos = lexicon.get(current_token.word);
+ pos = lexicon.get(current_token.word);
+
+ // System.out.println(current_token.word+" "+current_token.pos);
+ Double freq=lexicon.get(current_token.word).get((Byte)posMap.get(current_token.pos));
+ // if a given POS is already in its values, then add its corresponding count, otherwise add a POS value with a count of 1
+ pos.put((Byte)posMap.get(current_token.pos), (freq == null) ? 1 : freq + 1);
+ // System.out.println(pos.get(posMap.get(current_token.pos)));
+ counts.put(current_token.word, counts.get(current_token.word)+1);
+ } // if a token is unknown yet
+ else {
+ // Map<String, Double> pos = new HashMap<String, Double>();
+ pos.put((Byte)posMap.get(current_token.pos),new Double(1));
+ counts.put(current_token.word, new Integer(1));
+ lexicon.put(current_token.word, pos);
+ }
+ }
+ System.out.println(tokens_count_all_corpus);
+ return lexicon;
+ }
+
+ /**
+ * Convert posList to a byte array, and operate further on bytes.
+ * Preserver original mapping in a hashmap
+
+ byte [] b;
+ private void getBytes(List pos){
+ String [] classes = (String []) pos.toArray(new String[pos.size()]);
+ for(int i = 0; i<classes.length; i++)
+ b = classes[i].getBytes(); //getBytes from string
+
+ }
+
+ */
+
+ /**
+ * a hashmap for string-bytes ? matching
+ */
+
+ // static Map mapping = new HashMap<String, Byte>();
+ // static byte b = 0;
+
+ private Map getHashmap(List posList){
+ byte b = 0;
+ // String [] classes = (String []) posList.toArray(new String[posList.size()]);
+ for(int i = 0; i<posList.size(); i++) {
+ if (!posMap.containsKey(posList.get(i))){
+ posMap.put(posList.get(i), b);
+ // mapping.put(classes[i],b);
+ b+=1;
+ }
+ } return posMap;
+ }
+
+ /*
+ private Map<String, Map<Byte,Double>> convertLexicon(Map<String, Map<String, Double>> words) {
+ Map<String, Map<Byte,Double>>convertedWords = new HashMap<String, Map<Byte,Double>>();
+ Iterator<Entry<String, Map<String, Double>>> keyValuePairs = words.entrySet().iterator(); // iterate over words
+ for (int i = 0; i < words.size(); i++)
+ {
+ Map.Entry<String, Map<String, Double>> entry = (Map.Entry<String, Map<String, Double>>) keyValuePairs.next();
+ Object key = entry.getKey();
+
+ Map<String, Double> pos2= words.get(key); // map of possible pos-s of the word
+
+ Iterator<Entry<String, Double>> keyValuePairs_pos = pos2.entrySet().iterator(); // iterate over words
+ Map lokal = new HashMap();
+ for (int u = 0; u < pos2.size(); u++)
+ {
+
+ return convertedWords;
+ }
+ */
+
+
+ /**
+ * Computes {@code word_probs} using {@link #get_lexicon(List)} frequency counts for known words..
+ * TO_DO: ADD SMOOTHING FOR UNKNOWNS?? OR add smoothing directly when come across unknown..
+ */
+
+ transient Map sm = new HashMap ( ) ; // suffix map for non-capitalized words
+ transient Map sm2 = new HashMap ( ); // suffix map for capitalized;
+ @SuppressWarnings("unchecked")
+ public List get_word_probs(Map<String,Map<Byte, Double>> corpus){
+
+ Map word_counts=corpus;
+ //System.out.println(word_counts.entrySet().toString());
+ Map word_probs = new HashMap<String, Map<String,Double>>();
+
+ int mapsize = word_counts.size();
+
+ Iterator<Entry<String, Map>> keyValuePairs = word_counts.entrySet().iterator(); // iterate over words
+ Map<String, Double> pos_counts = get_ngrams(1);
+
+ for (int i = 0; i < mapsize; i++)
+ {
+ Map.Entry<String, Map> entry = (Map.Entry<String, Map>) keyValuePairs.next();
+ Object key = entry.getKey();
+
+ Map pos2= (Map) word_counts.get(key); // map of possible pos-s of the word
+
+ Iterator<Entry<String, Double>> keyValuePairs_pos = pos2.entrySet().iterator(); // iterate over words
+ Map lokal = new HashMap();
+ for (int u = 0; u < pos2.size(); u++)
+ {
+ Map.Entry entry_pos = (Map.Entry) keyValuePairs_pos.next();
+ Object key2 = entry_pos.getKey(); // pos of a word
+ // System.out.println(key2);
+
+ // if (!key2.equals("count")) {
+ // byte b = (Byte)posMap.get(key2);
+ Object value2 = entry_pos.getValue(); // its count
+ // System.out.println(pos_counts);
+ double freq_pos=pos_counts.get(key2);
+ Double val2 = (Double)value2 / freq_pos; // Prob(w|t) = freq(w,t)/freq(t)
+ // lokal.put((String)key2, val2); // save probability as a log2
+ lokal.put(key2, val2); //
+ // } else {
+ // lokal.remove("count");
+ // }
+ }
+ // insert the word and its corresponding tags as well as their common probabilities into the words maps
+ word_probs.put((String)key, lokal);
+
+ /**
+ * Get suffix probabilities from the words with frequency lower than 10 in the corpus
+ */
+ Set local_suffixes = new HashSet();
+
+ // We maintain two different suffix counts for capitalized and non-capitalized words
+
+ Set local_suffixes_capitalized = new HashSet();
+
+ // here we get words with counts under 10 for suffix probabilities.. the condition can be changed upt o you..
+ if ((Integer)(counts.get(key))<10){
+
+ SuffixTree st = new SuffixTree((String) key);
+
+ Iterator<Entry> kv = st.edges.entrySet().iterator();
+
+ for (int f= 0; f<st.edges.size();f++){
+
+ Map.Entry m = (Map.Entry) kv.next();
+ // Object keys = m.getKey();
+ SuffixTree.Edge e = (SuffixTree.Edge) m.getValue();
+
+ if (st.nodes.get(e.end_node-1).suffix_node == -1){
+
+ String suffix = st.text.substring(e.first_char_index,e.last_char_index+1);
+
+ if (capitalized((String)key)){
+ local_suffixes_capitalized.add(suffix);
+ } else {
+ local_suffixes.add(suffix);
+ }
+ }
+ }
+ }
+
+ // if this word is relevant for suffix tree
+ if (!local_suffixes.isEmpty() | !local_suffixes_capitalized.isEmpty()){
+ Set endings;
+ Map local_sm = new HashMap ( );
+ if (local_suffixes.isEmpty()){
+ endings = local_suffixes_capitalized;
+ local_sm = sm2;
+ } else {
+ endings = local_suffixes;
+ local_sm = sm;
+ }
+ Iterator it = endings.iterator();
+ // insert or update suffix probabilities
+ while (it.hasNext()){
+ Object element = it.next();
+
+ //for (int u = 0; u< local_suffixes.size(); u++){
+ Map etwas = new HashMap();
+
+ if(local_sm.containsKey(element)){
+ Map pos_suffix = new HashMap();
+
+ // get map of possible pos-s of the suffix
+ pos_suffix= (Map) local_sm.get(element);
+ Iterator<Entry> pos_suf = pos_suffix.entrySet().iterator(); // iterate over words
+
+
+ for (int k = 0; k < pos_suffix.size(); k++)
+ {
+ Map.Entry entry3 = (Map.Entry) pos_suf.next();
+
+ Object key_pos = entry3.getKey(); // pos of a suffix
+ // System.out.println(key_pos);
+ // System.out.println(key_pos);
+ // byte b = (Byte)posMap.get(key_pos);
+
+ Object value_pos = entry3.getValue(); // its probability count
+
+
+ // If a given pos of a suffix is also present in the pos-s of a corresponding word
+ // then add both up
+
+ if (((Map)word_probs.get(key)).containsKey(key_pos)){
+ Double val_suffix = (Double)value_pos + (Double)((Map)word_probs.get(key)).get(key_pos); // Prob(w|t) = freq(w,t)/freq(t)
+ // etwas.put((String)key_pos, val_suffix);
+ etwas.put(key_pos, val_suffix);
+ } else {
+ // etwas.put((String)key_pos, (Double)value_pos);
+ etwas.put(key_pos, value_pos);
+ }
+ // add the pos of a corresponding word with its probability into the suffix map,
+ // (which is not yet present in the poss of the suffix)
+
+ Set smth2 = ((Map)word_probs.get(key)).keySet();
+ Object [] smth = smth2.toArray();
+
+ for (int r=0; r<smth.length;r++){
+ if (!pos_suffix.containsKey(smth[r]) && !smth[r].equals("count")){
+ // b = (Byte)posMap.get(smth[r]);
+ // etwas.put((String)smth[r], pos2.get(smth[r]));
+ etwas.put(smth[r], pos2.get(smth[r]));
+ }
+ }
+ }
+ } else {
+ etwas.putAll(lokal);
+ }
+ if (local_suffixes.isEmpty()){
+ sm2.put(element, etwas);;
+ } else {
+ sm.put(element, etwas);;
+ }
+ //local_sm.put(element, etwas);
+ }
+ }
+
+
+ }
+ List l = new ArrayList<Map>();
+ l.add(word_probs); //add word probabilities
+ l.add(sm); // add suffixes of non-capitalized words
+ l.add(sm2); // add suffixes of capitalized words
+
+ return l;
+ }
+
+ /**
+ * Make LOGs out of probabilities.. there was a reason to separate it from the get_word_probs method at the initial step
+ *
+ */
+ /*
+ @SuppressWarnings("unchecked")
+private Map<String,Map<String, Double>> logify_probs(Map<String,Map<String, Double>> probs){
+
+ Map<String,Map<String, Double>> logs = new HashMap<String, Map<String,Double>>();
+
+ Iterator<Entry<String, Map<String, Double>>> keyValuePairs = probs.entrySet().iterator(); // iterate over words
+
+ for (int i = 0; i < probs.size(); i++)
+ {
+ Map.Entry<String, Map<String, Double>> entry = (Map.Entry<String, Map<String, Double>>) keyValuePairs.next();
+ Object key = entry.getKey();
+ Map<String, Double> poss= probs.get(key); // map of possible pos-s of the word
+
+ Object [] pos_s = poss.entrySet().toArray(); // for iteration over possible pos_s
+
+ for (int u = 0; u < pos_s.length; u++)
+ {
+
+ Map.Entry entry2 = (Map.Entry) pos_s[u];
+ // System.out.println(entry);
+ Object key2 = entry2.getKey(); // pos of a word
+
+ Double value2 = (Double) entry2.getValue(); // its count
+ poss.put((String)key2, Math.log(value2)); // save probability as a log2
+ }
+ // insert the word and its corresponding tags as well as their common probabilities into the words maps
+ logs.put((String)key, poss);
+
+ }
+ return logs;
+ }*/
+
+ /* Helper class
+ *
+
+
+ class CompoundKey{
+
+ private byte [] keys;
+
+ private CompoundKey(byte [] vals){
+ initArray(vals);
+ }
+ private void initArray(byte [] numbers){
+ this.keys = numbers;
+ }
+
+ /**
+ * @see java.lang.Object#equals(java.lang.Object)
+
+ @Override
+ public boolean equals(Object object) {
+
+ CompoundKey key = (CompoundKey) object;
+
+ String s1 = hardwareClassname;
+ String s2 = key.hardwareClassname;
+ if (s1 != null && s1.equals(s2)) {
+ String t1 = hardwareDriverType;
+ String t2 = key.hardwareDriverType;
+
+ if (t1 != null && t1.equals(t2)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * @see java.lang.Object#hashCode()
+
+ @Override
+ public int hashCode() {
+ int hashCode = (hardwareClassname + hardwareDriverType).hashCode();
+ //int hashCode = 1;
+
+ return hashCode;
+ }
+
+ /**
+ * @see java.lang.Object#toString()
+
+ @Override
+ public String toString() {
+ return hardwareClassname + ", " + hardwareDriverType;
+ }
+
+
+ }*/
+
+ /**
+ * Computes N-gram frequencies
+ * @param N
+ * @return Map<String, Double> N-grams of parts-of-speech, where {@code N = 1, 2 or 3}
+ * @throws IllegalArgumentException
+ */
+ private Map get_ngrams(int N) throws IllegalArgumentException{
+
+ Map ngrams1= new HashMap();
+ Map ngrams2= new HashMap();
+ Map ngrams3= new HashMap();
+
+ if (N==1){
+ for (int y=0; y<posList.size(); y++){
+ // Double freq= (Double)ngrams1.get(posList.get(y));
+ byte b = (Byte)posMap.get(posList.get(y));
+ Double freq= (Double)ngrams1.get(b);
+
+ // if a given POS is already in the Map, then add its corresponding count, otherwise add a POS value with a count of 1
+ ngrams1.put(b, (freq == null) ? 1 : freq + 1);
+ }
+ }
+ else if (N==2){
+
+ for (int y=0; y<(posList.size()-1); y++){
+ List b_key = new ArrayList<Byte>(2);
+ Byte b2 = (Byte) posMap.get(posList.get(y+1));
+ Byte b1 = (Byte) posMap.get(posList.get(y));
+
+ // String s2 = posList.get(y)+"_"+posList.get(y+1);
+
+ b_key.add(b1);
+ b_key.add(b2);
+ // Double freq= (Double)ngrams2.get(s2);
+ Double freq= (Double)ngrams2.get(b_key);
+
+ // System.out.println(b_key.toString());
+ // System.out.println(ngrams2.containsKey(b_key));
+
+ ngrams2.put(b_key, (freq == null) ? 1 : freq + 1);
+ }
+ }
+ else if (N==3){
+ for (int y=0; y<(posList.size()-2); y++){
+ // String s3 = posList.get(y)+"_"+posList.get(y+1)+"_"+posList.get(y+2);
+ List b_key = new ArrayList<Byte>(2);
+
+ byte b1 = (Byte)posMap.get(posList.get(y));
+ byte b2 = (Byte)posMap.get(posList.get(y+1));
+ byte b3 = (Byte)posMap.get(posList.get(y+2));
+ // String s2 = posList.get(y)+"_"+posList.get(y+1);
+
+ b_key.add(b1);
+ b_key.add(b2);
+ b_key.add(b3);
+
+ Double freq= (Double)ngrams2.get(b_key);
+ // Double freq= (Double)ngrams3.get(s3);
+ ngrams3.put(b_key, (freq == null) ? 1 : freq + 1);
+ }
+ } else{
+ throw new IllegalArgumentException ("N=1, N=2 or N=3, no further N-grams are supported at the moment");
+ }
+ return ((N==1)? ngrams1: (N == 2) ? ngrams2 : ngrams3);
+ }
+
+ // @SuppressWarnings("unchecked")
+ /**
+ * Computes {@code transition_probs} using {@link #get_ngrams(int)} frequency counts for N-grams..
+ */
+
+ Map<String, Double> unigrams;
+ Map<String, Double> bigrams;
+ Map<String, Double> trigrams;
+
+ @SuppressWarnings("unchecked")
+public Map get_transition_probs(int N) throws IllegalArgumentException{
+ Map probs1= new HashMap();
+ Map probs2= new HashMap();
+ Map probs3= new HashMap();
+ unigrams = get_ngrams(1);
+ bigrams = get_ngrams(2);
+ trigrams = get_ngrams(3);
+
+ if (N==1) {
+ Iterator keyValuePairs = unigrams.entrySet().iterator();
+ for (int i = 0; i < unigrams.size(); i++) // for all bigrams
+ {
+ Map.Entry entry = (Map.Entry) keyValuePairs.next();
+ Object key = entry.getKey(); // get a bigram
+ double freq1 = unigrams.get(key); // get a count of a unigram
+ double prob1 = (Double)freq1 / tokens_count_all_corpus; // Prob(key) = freq(tag)/freq(all_tags)?
+ probs1.put(key, prob1); // save probability as a log2 : Math.log(prob1)
+
+ }
+ }
+
+ else if (N==2){
+
+ Iterator keyValuePairs = bigrams.entrySet().iterator();
+ for (int i = 0; i < bigrams.size(); i++) // for all bigrams
+ {
+ Map.Entry entry = (Map.Entry) keyValuePairs.next();
+ ArrayList key = (ArrayList) entry.getKey(); // get a bigram
+ // String [] t = ((String)key).split("_");
+ // double freq1 = unigrams.get(t[0]); // get a count of a preceding unigram
+ double freq1 = unigrams.get(key.get(0));
+ Object freq2 = entry.getValue(); // get a count of a bigram
+
+ double prob2 = (Double)freq2 / freq1; // Prob(t2|t1) = freq(t1,t2)/freq(t1)
+ probs2.put(key, prob2); // save probability as a log2: Math.log(prob2)
+ }
+ } else if (N==3){ // for trigram models
+
+ Iterator keyValuePairs = trigrams.entrySet().iterator();
+ for (int i = 0; i < trigrams.size(); i++) // for all trigrams
+ {
+ Map.Entry entry = (Map.Entry) keyValuePairs.next();
+ ArrayList key = (ArrayList) entry.getKey(); // get a trigram
+ // String [] t = ((String)key).split("_");
+ // String tt = t[0]+"_"+t[1];
+
+ Double freq1 = bigrams.get(key.subList(0, 2)); // get a count of a preceding bigram
+
+ Object freq2 = entry.getValue(); // get a count of a trigram
+
+ double prob3 = (Double)freq2/freq1; // Prob(t3|(t1_t2)) = freq(t1_t2_t3)/freq(t1_t2)
+ probs3.put(key, prob3); // save probability as a log2: Math.log(prob3)
+ }
+ } else{
+ throw new IllegalArgumentException ("only uni-, bi-, and trigramms are supported at the moment");
+ }
+ return ((N == 2) ? probs2 : (N==3)? probs3 : probs1);
+ }
+
+
+
+ /**
+ * Computes alphas for linear interpolation smoothing of unknown n-grams
+ * @param N N-gram
+ * currently lambdas are calculated as in (Brants, 2000)
+ */
+
+ public double [] calculate_lambda(int N){
+ double lambda1 = 0;
+ double lambda2 = 0;
+ double lambda3 = 0;
+
+ double count2 = 0;
+ double count3 = 0;
+
+ if (N ==2) {
+ Iterator keyValuePairs = bigrams.entrySet().iterator();
+ for (int i = 0; i < bigrams.size(); i++) // for all bigrams
+ {
+ Map.Entry entry = (Map.Entry) keyValuePairs.next();
+ ArrayList key = (ArrayList) entry.getKey(); // get a bigram
+ // String [] t = ((String)key).split("_");
+ double freq1 = unigrams.get(key.get(0)); // get a count of a preceding unigram
+ Double freq2 = (Double) entry.getValue(); // get a count of a bigram
+
+ double f2 = (freq2-1)/(freq1-1);
+ double f1 = (freq1-1)/(tokens_count_all_corpus-1);
+
+ double freq = get_max(f2, f1, 0);
+
+ if (freq == f2){lambda2+=freq2;count2+=freq2;}
+ else {lambda1+=freq2;count2+=freq2;}
+ } lambdas2[0] = lambda1/count2; lambdas2[1]= lambda2/count2;
+ }
+
+ if (N == 3) {
+
+ Iterator keyValuePairs = trigrams.entrySet().iterator();
+ for (int i = 0; i < trigrams.size(); i++) // for all trigrams
+ {
+ Map.Entry entry = (Map.Entry) keyValuePairs.next();
+ ArrayList key = (ArrayList) entry.getKey(); // get a trigram
+ // String [] t = ((String)key).split("_");
+ // String tt = t[0]+"_"+t[1];
+
+ Double freq2 = bigrams.containsKey(key.subList(0, 3)) ? bigrams.get(key.subList(0, 3)) : 0.0; // get a count of a preceding bigram
+ Double freq3 = (Double) entry.getValue(); // get a count of a trigram
+ Double freq1 = unigrams.containsKey(key.get(0)) ? unigrams.get(key.get(0)) : 0.0;
+
+ double f3 = (freq3-1)/(freq2-1);
+ double f2 = (freq2-1)/(freq1-1);
+ double f1 = (freq1-1)/(tokens_count_all_corpus-1);
+ double freq = get_max(f3, f2, f1);
+ if (freq == f3) {lambda3+= freq3; count3+=freq3;} // or just real frequency?
+ else if (freq == f2){lambda2+=freq3; count3+=freq3;}
+ else {lambda1+=freq3;count3+=freq3;}
+ } lambdas3[0] = lambda1/count3; lambdas3[1]=lambda2/count3; lambdas3[2]=lambda3/count3;
+ }
+ System.out.println("lambdas for 2-grams = "+lambdas2[0]+" "+lambdas2[1]+"\n"+"lambdas for 3-grams"+lambdas3[0]+" "+lambdas3[1]+" "+lambdas3[2]);
+ return ((N == 2) ? lambdas2 : lambdas3);
+ }
+
+ private double get_theta (Map<String, Double> m) {
+ double d = 0;
+ double sum1 = 0;
+ double tagset_size = m.size();
+ Iterator tags_probs = m.entrySet().iterator();
+ for (int h = 0; h<tagset_size; h++){
+ Map.Entry entry_pos = (Map.Entry) tags_probs.next();
+ // Object key_pos = entry_pos.getKey();
+ Double prob = (Double) entry_pos.getValue();
+ sum1+=prob;
+ }
+ double prob_average = sum1/tagset_size;
+ double sum2 = 0;
+
+ Iterator tags_probs2 = m.entrySet().iterator();
+ for (int h = 0; h<tagset_size; h++){
+ Map.Entry entry_pos = (Map.Entry) tags_probs2.next();
+ Double prob = (Double) entry_pos.getValue();
+ sum2+=Math.pow((prob-prob_average),2);
+ }
+ d = sum2/(tagset_size-1);
+
+ return d;
+ }
+
+ private double get_max(double a, double b, double c){
+ double max = a;
+ if (b>max){ max = b; }
+ if (c>max) {max = c; }
+ return max;
+ }
+
+ /**
+ * Writes the model to a binary file
+ * @param filename output file name
+ */
+
+ private void write_to_file(String filename){
+
+ File file = null;
+ if (filename!=null) { file = new File (filename);}
+ // or use a default file name
+ if (file == null) {
+ System.out.println ("Default: model.dat");
+ file = new File ("model.dat");
+ }
+
+ try {
+ // Create an output stream to the file.
+ FileOutputStream file_output = new FileOutputStream (file);
+ ObjectOutputStream o = new ObjectOutputStream( file_output );
+ o.writeObject(this);
+
+ file_output.close ();
+ }
+ catch (IOException e) {
+ System.err.println ("IO exception = " + e );
+ }
+
+ }
+
+ private void init(){
+
+ List<Map<String, Map<String,Double>>> l = get_word_probs(get_lexicon(corpus));
+
+ this.word_probs = (Map) l.get(0);
+ this.suffix_tree = (Map) l.get(1);
+ this.suffix_tree_capitalized = (Map) l.get(2);
+ this.counts.entrySet().toString();
+ Map test2 = get_ngrams(2);
+ Map test3 = get_ngrams(3);
+ Map test1 = get_ngrams(1);
+ /* Iterator<Entry<String, Map>> it = test2.entrySet().iterator(); // iterate over words
+
+ for (int g = 0; g<test2.size(); g++){
+
+ Map.Entry entry = (Map.Entry) it.next();
+ ArrayList key = (ArrayList ) entry.getKey();
+ Object value = entry.getValue();
+ System.out.println(key.toString());
+ System.out.println(value);
+ }*/
+ System.out.println("Number of ngrams: "+(test2.size()+test1.size()+test3.size()));
+ System.out.println("Number of different words "+word_probs.size());
+ System.out.println("Number of non-capitalized suffixes: "+suffix_tree.size());
+ System.out.println("Number of capitalized suffixes: "+suffix_tree_capitalized.size());
+
+ Map pos_probabilities = get_transition_probs(1);
+ this.transition_probs.putAll(pos_probabilities);
+ this.transition_probs.putAll(get_transition_probs(2));
+ this.transition_probs.putAll(get_transition_probs(3));
+
+ this.theta = get_theta(pos_probabilities);
+ System.out.println("theta= "+this.theta);
+ this.lambdas2 = calculate_lambda(2);
+ this.lambdas3 = calculate_lambda(3);
+ write_to_file(this.OutputFile);
+ }
+
+ public static void main(String[] args) {
+
+ // PennReader penn = new PennReader("F:/pos/wsj/training");
+ // BrownReader brown = new BrownReader("../brown");
+ TT_FormatReader tiger = new TT_FormatReader("D:/Jane/IBM/Tagger_komplett/tueba_tigerFormat.txt");
+ ModelGenerationBytes md = new ModelGenerationBytes(tiger.corpus, "test.dat");
+ md.init();
+
+ }
+
+}
+
Added: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/SuffixTree.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/SuffixTree.java?rev=617123&view=auto
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/SuffixTree.java (added)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/SuffixTree.java Thu Jan 31 05:00:08 2008
@@ -0,0 +1,325 @@
+/*
+ *Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+package org.apache.uima.examples.tagger;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Java implementation of the Ukkonen's suffix tree (the fastest known suffix tree, O(n)) inspired
+ * by Mark Nelson's http://marknelson.us/1996/08/01/suffix-trees/
+ */
+public class SuffixTree {
+
+ String text = "";
+
+ List<Node> nodes = new ArrayList<Node>();
+
+ Map edges = new HashMap(); // Map to store the starting node of the edges and their corresponding
+ // first characters
+
+ char[] chars;
+
+ public SuffixTree() {
+ this("");
+ }
+
+ Suffix active_point = new Suffix(0, 0, -1); // initial active point is the first non-leaf suffix
+ // in the tree
+
+ public SuffixTree(String text) {
+ // int token_begin = words.length();
+
+ nodes.removeAll(nodes);
+
+ this.text = text;
+ chars = text.toCharArray();
+
+ for (int i = 0; i < chars.length; i++) {
+ add_prefix(i, active_point); //
+ }
+ }
+
+ //
+ public void insert_edge(Edge edge) {
+ List keys = new ArrayList();
+ keys.add(edge.start_node);
+ keys.add(chars[edge.first_char_index]);
+ edges.put(keys, edge);
+ }
+
+ /**
+ *
+ * Internal Class SUFFIX
+ */
+
+ class Suffix {
+
+ int origin_node;
+
+ int first_char_index;
+
+ int last_char_index;
+
+ public Suffix(int node, int begin, int end) {
+ this.origin_node = node;
+ this.first_char_index = begin;
+ this.last_char_index = end;
+ }
+
+ boolean isExplicit() {
+ return first_char_index > last_char_index;
+ }
+
+ boolean isImplicit() {
+ return last_char_index >= first_char_index;
+ }
+
+ // "The canonical representation of the suffix simply requires that the origin_node
+ // in the Suffix object be the closest parent to the end point of the string.
+ // This means that the suffix string represented by the pair (0, "ABABABC"),
+ // would be canonized by moving first to (1, "ABABC"), then (4, "ABC"), and finally (8,"").
+ // When a suffix string ends on an explicit node, the canonical representation will use an empty
+ // string
+ // to define the remaining characters in the string.
+ //
+ // An empty string is defined by setting first_char_index to be greater than last_char_index.
+ // When this is the case, we know that the suffix ends on an explicit node.
+ // If first_char_index is less than or equal to last_char_index,
+ // it means that the suffix string ends on an implicit node."
+ // (Mark Nelson. Fast String Searching With Suffix Trees.
+ // http://marknelson.us/1996/08/01/suffix-trees/)
+
+ void canonize() {
+ if (!this.isExplicit()) {
+ List keys = new ArrayList();
+ keys.add(this.origin_node);
+ keys.add(chars[this.first_char_index]);
+ Edge edge = (Edge) edges.get(keys);
+
+ int edge_span = edge.last_char_index - edge.first_char_index + 1;
+
+ int suffix_span = this.last_char_index - this.first_char_index + 1;
+
+ if (edge_span <= suffix_span) {
+ this.first_char_index = this.first_char_index + edge_span;
+ this.origin_node = edge.end_node;
+ this.canonize();
+
+ }
+ }
+ }
+ }
+
+ /**
+ * Internal Class EDGE
+ */
+
+ class Edge {
+ int first_char_index;
+
+ int last_char_index;
+
+ int start_node;
+
+ int end_node;
+
+ public Edge(int parent_node, int end_node, int first_char_index, int last_char_index) {
+ this.first_char_index = first_char_index;
+ this.last_char_index = last_char_index;
+ this.start_node = parent_node;
+ this.end_node = end_node;
+ }
+
+ // When a suffix ends on an implicit node, adding a new character
+ // means I have to split an existing edge.
+ // The existing edge loses its parent, as well as some of its leading
+ // characters. The newly created edge descends from the original
+ // parent, and now has the existing edge as a child.
+ //
+ // Since the existing edge is getting a new parent and starting
+ // character, it is re-inserted.
+ //
+ // The number of characters stolen from the original node and given
+ // to the new node is equal to the number of characters in the suffix
+ // argument, which is last - first + 1;
+
+ // Comment to the suffix pointers: The suffix pointers are built at the same time the update to
+ // the tree is taking place.
+ // As I move from the active point to the end point, I keep track of the parent node of each of
+ // the new leaves I create.
+ // Each time I create a new edge, I also create a suffix pointer
+ // from the parent node of the last leaf edge I created to the current parent edge.
+
+ public int split_edge(Suffix suffix) {
+
+ Node next = new Node();
+ nodes.add(next);
+
+ int new_node_index = nodes.size();
+
+ int suf_span = suffix.last_char_index - suffix.first_char_index + 1;
+ nodes.get(new_node_index - 1).suffix_node = suffix.origin_node;
+ Edge new_edge = new Edge(new_node_index, this.end_node, this.first_char_index + suf_span,
+ this.last_char_index);
+ insert_edge(new_edge);
+
+ // SuffixTree.remove_edge(this.start_node, this.first_char_index);
+ // shorten existing edge
+ this.last_char_index = this.first_char_index + suf_span - 1;
+ // this.end_node = new_node_index;
+
+ insert_edge(new Edge(this.start_node, new_node_index, this.first_char_index,
+ this.last_char_index));
+
+ return new_node_index; // return the new origin node index of the last edge
+ }
+
+ }
+
+ /**
+ * Internal Class NODE
+ */
+
+ // The only information contained in a node is the
+ // suffix link. Each suffix in the tree that ends
+ // at a particular node can find the next smaller suffix
+ // by following the suffix_node link to a new node. Nodes
+ // are stored in a simple array.
+ class Node {
+ int suffix_node;
+
+ // static int count=0;
+
+ // Nodes with suffix link of (-1) are leaf nodes
+ public Node() {
+ suffix_node = -1;
+ }
+
+ }
+
+ public void add_prefix(int last_char, Suffix active_point) {
+ int last_parent_node = -1;
+ int parent_node = 0;
+
+ for (;;) {
+ parent_node = active_point.origin_node;
+
+ Edge edge;
+ if (active_point.isExplicit()) {
+ List keys = new ArrayList();
+ keys.add(active_point.origin_node);
+ keys.add(chars[last_char]);
+ if (edges.containsKey(keys)) {
+ edge = (Edge) edges.get(keys);
+ break;
+ }
+ } else if (active_point.isImplicit()) { // if suffix is implicit, i.e. it does not end in a
+ // leaf node $
+ List keys2 = new ArrayList();
+ keys2.add(active_point.origin_node);
+ keys2.add(chars[active_point.first_char_index]);
+ edge = (Edge) edges.get(keys2);
+
+ int span = active_point.last_char_index - active_point.first_char_index;
+ // if the given prefix is already in the tree, do nothing
+ if (chars[edge.first_char_index + span + 1] == chars[last_char]) {
+ break;
+ } else {
+ parent_node = edge.split_edge(active_point);
+ }
+
+ }
+
+ Node next = new Node();
+ nodes.add(next);
+ int new_node_index = nodes.size();
+ edge = new Edge(parent_node, new_node_index, last_char, chars.length - 1);
+ insert_edge(edge);
+
+ // When we create a new node, it also means we need to create a suffix link to the new node
+ // from
+ // the last node we visited.
+ if (last_parent_node > 0) {
+ nodes.get(last_parent_node - 1).suffix_node = parent_node;
+ }
+ last_parent_node = parent_node;
+
+ // here we move to the next smaller suffix
+ if (active_point.origin_node == 0) {
+ active_point.first_char_index += 1;
+ } else {
+
+ active_point.origin_node = nodes.get(active_point.origin_node - 1).suffix_node;
+
+ }
+ active_point.canonize();
+ }
+ if (last_parent_node > 0) {
+ nodes.get(last_parent_node - 1).suffix_node = parent_node;
+ }
+ active_point.last_char_index += 1;
+ active_point.canonize();
+ }
+
+ // ///////// TEST
+
+ /*
+ * public void walk_tree(SuffixTree suffix_tree, int current_node_index, Suffix current_suffix,
+ * int current_suffix_len){ int edge_count = 0; Set alphabet = new HashSet<Character>(); char []
+ * chars = text.toCharArray(); for (char c : chars){ if(!alphabet.add(c)){ // }
+ * System.out.println(alphabet.toString()); Character [] letters = (Character [])
+ * alphabet.toArray(); for (char ch : letters){ try { List keys = new ArrayList();
+ * keys.add(current_node_index); keys.add(ch); Edge edge = (Edge) suffix_tree.edges.get(keys); if
+ * (current_node_index != edge.start_node){ System.err.println("ERROR"); }
+ * System.out.println(current_node_index+" "+edge.start_node); edge_count+=1; int l =
+ * current_suffix_len; for (int j : Range((Comparable)edge.last_char_index, (Comparable)
+ * (edge.first_char_index+1))){ current_suffix. = suffix_tree.text.charAt(j); } } } }
+ * }
+ *
+ *
+ *
+ *
+ *
+ *
+ * public static void main(String[] args) {
+ *
+ * String test_str="pace"; SuffixTree suffix_tree = new SuffixTree(test_str);
+ *
+ *
+ * System.out.println(edges.keySet().toString());
+ *
+ * Iterator<Entry> kv = edges.entrySet().iterator(); for (int u= 0; u<edges.size();u++){
+ *
+ * Map.Entry m = (Map.Entry) kv.next(); Object key = m.getKey(); Edge e = (Edge) m.getValue();
+ *
+ * if (nodes.get(e.end_node-1).suffix_node == -1){ System.out.println(key);
+ *
+ * System.out.println("suffix_node "+nodes.get(e.end_node-1).suffix_node);
+ * System.out.println("test "+chars[e.first_char_index]);
+ *
+ * System.out.println(test_str.subSequence(e.first_char_index,e.last_char_index+1));
+ * } }
+ * }
+ */
+}
Added: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TT_FormatReader.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TT_FormatReader.java?rev=617123&view=auto
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TT_FormatReader.java (added)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TT_FormatReader.java Thu Jan 31 05:00:08 2008
@@ -0,0 +1,72 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * Tree Tagger Format Reader: a word per line with possibly html-tags,
+ * which are ignored and 2/3 columns separated by tabs.
+ * Columns are: "word \t tag \t lemma"
+ *
+ */
+
+package org.apache.uima.examples.tagger;
+
+import java.io.BufferedReader;
+import java.io.FileReader;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+public class TT_FormatReader {
+
+ List<Token> corpus;
+
+ public TT_FormatReader(String InputFile) {
+ corpus = read_corpus(InputFile);
+
+ }
+
+ public static List<Token> read_corpus(String file) {
+
+ // Text is already tokenized
+
+ int line_count = 0;
+ String line;
+ List<Token> text = new ArrayList<Token>();
+ try {
+ BufferedReader in = new BufferedReader(new FileReader(file));
+
+ while ((line = in.readLine()) != null) {
+ if (line.trim().length() > 0) {
+ line_count += 1;
+ String[] t = line.split("\t");
+ if (t.length >= 2) {
+ Token token = new Token(t[0], t[1]);
+ text.add(token);
+ }
+ }
+ }
+ in.close();
+ } catch (IOException e) {
+ System.out.println(e);
+ return null;
+ }
+
+ return text;
+ }
+}
Added: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TagMapping.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TagMapping.java?rev=617123&view=auto
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TagMapping.java (added)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/TagMapping.java Thu Jan 31 05:00:08 2008
@@ -0,0 +1,72 @@
+/*
+ *Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+package org.apache.uima.examples.tagger;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ */
+public class TagMapping {
+
+ public static List<Token> map_tags(List<Token> tokens) {
+
+ // for (int i=0; i<sentences.size(); i++){ // iterate over sentences
+
+ List<Token> tokens2 = new ArrayList<Token>(tokens.size());
+
+ for (int x = 0; x < tokens.size(); x++) { // iterate over tokens of the sentence with their
+ // corresponding POS
+ Token current_token = tokens.get(x);
+ String[] z = new String[2];
+ if (current_token.pos.contains("+")) {
+ z = current_token.pos.split("[+]");
+ current_token.pos = z[0];
+ }
+ // for cases like : BEZ*
+ if (current_token.pos.contains("*") && !(current_token.pos.startsWith("*"))) {
+ z[0] = current_token.pos.replace("*", "");
+ current_token.pos = z[0];
+ }
+
+ // for: *-h1
+ if (current_token.pos.startsWith("*")) {
+ z[0] = "*";
+ current_token.pos = z[0];
+ }
+ if (current_token.pos.contains("-") && !(current_token.pos.startsWith("--"))) {
+ z = current_token.pos.split("[-]");
+ current_token.pos = z[0];
+ }
+ if (current_token.pos.startsWith("--")) {
+ z[0] = "--";
+ current_token.pos = z[0];
+ }
+
+ Token zwischen = new Token(current_token.word, current_token.pos);
+
+ tokens2.add(zwischen);
+ }
+ return tokens2;
+
+ }
+
+}
Modified: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Tagger.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Tagger.java?rev=617123&r1=617122&r2=617123&view=diff
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Tagger.java (original)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Tagger.java Thu Jan 31 05:00:08 2008
@@ -17,6 +17,10 @@
* under the License.
*/
+
+
+//
+
package org.apache.uima.examples.tagger;
import java.util.List;
@@ -26,6 +30,8 @@
* to compute the most probable path of parts of speech for a given sequence of tokens
* @see Viterbi
*/
+
+// AT THE MOMENT IS USELESS TODO: check if we need it at all..and integrate if :)
public interface Tagger {
Added: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Token.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Token.java?rev=617123&view=auto
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Token.java (added)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Token.java Thu Jan 31 05:00:08 2008
@@ -0,0 +1,44 @@
+/*
+ *Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+package org.apache.uima.examples.tagger;
+
+/**
+ *
+ */
+public class Token {
+
+ String pos;
+
+ String word;
+
+ public Token() {
+ this(null, null);
+ }
+
+ public Token(String word) {
+ this(word, null);
+ }
+
+ public Token(String word, String pos) {
+ this.word = word;
+ this.pos = pos;
+ }
+}
Modified: incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Viterbi.java
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Viterbi.java?rev=617123&r1=617122&r2=617123&view=diff
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Viterbi.java (original)
+++ incubator/uima/sandbox/trunk/Tagger/src/main/java/org/apache/uima/examples/tagger/Viterbi.java Thu Jan 31 05:00:08 2008
@@ -25,30 +25,27 @@
import java.util.List;
import java.util.Map;
+
+// TODO: extra tag for non-recognized symbols (for which neither word nor suffix is available)
+
/**
- * Viterbi Algorithm: Given a model and a sequence of observations, what is the most likely state
- * sequence in the model that produces the observations? N.B. requires that the probabilities are
- * stored as logs in the model
+ * Viterbi Algorithm: Given a model and a sequence of observations, what is the most likely
+ * sequence of states in the model that produces the observations?
*/
public class Viterbi {
- public Viterbi() {
- super();
- }
-
@SuppressWarnings("unchecked")
public static Map<String, List> init_probs(String END_OF_SENT_TAG, Map<String, Double> pos_s) {
Map<String, List> init_probs = new HashMap<String, List>();
double p_init = Math.log(1.0); // symbolic initial probability, at the
// moment equal for all tags
- // if (state==END_OF_SENT_TAG){
Iterator a_pos = pos_s.entrySet().iterator();
- for (int h = 0; h < pos_s.size(); h++) { // for each of them
+ for (int h = 0; h < pos_s.size(); h++) { // for each of available parts of speech
Map.Entry entry_init = (Map.Entry) a_pos.next();
String key_init = (String) entry_init.getKey(); // get the tag (state)
- Object value_init = entry_init.getValue(); // get its P(w|t), it#s logged
+ Double value_init = (Double) entry_init.getValue(); // get its P(w|t)
Double p_local = p_init; // get the 'initial' probability of this tag,
// it#s logged
List vpath_list = new ArrayList<String>();
@@ -57,21 +54,17 @@
// ".")
vpath_list.add(key_init);
- p = p_local + (Double) value_init; // Prob(this tag|beginning of sequence) x P(w|t)
+ p = p_local + Math.log(value_init); // Prob(this tag|beginning of sequence) x P(w|t)
init_list.add(p);
init_list.add(vpath_list);
init_list.add(p);
init_probs.put(key_init, init_list);
}
- // }
- // else {
- // TODO
-
- // }
return init_probs;
}
-
+
+
/**
* @param N
* @param sentence
@@ -79,12 +72,13 @@
* @param pos_s
* @param transition_probs
* @param word_probs
+ * @param lambdas2, lambdas3
* @return
*/
@SuppressWarnings("unchecked")
public static List process(int N, List<String> sentence, String END_OF_SENT_TAG,
- List<String> pos_s, Map<String, Double> transition_probs,
- Map<String, Map<String, Double>> word_probs) {
+ Map<String, Map<String, Double>> suffix_tree,Map<String,Map<String, Double>> suffix_tree_cap, Map<String, Double> transition_probs,
+ Map<String, Map<String, Double>> word_probs, double[] lambdas2, double[] lambdas3, double theta) {
sentence.add(0, END_OF_SENT_TAG);
@@ -92,11 +86,12 @@
Map<String, List> all = new HashMap<String, List>(); // saves paths to the
// current token
-
+ // int cardinals = 0;
/** ********************************************************* */
/** * */
/** ********************************************************* */
-
+
+
for (int i = 0; i < sentence.size() - 1; i++) { // for every token (observation) in a sentence
/*
@@ -104,115 +99,239 @@
* them all equal 1.0 through the init_probs() function
*/
Map<String, Double> available_pos = new HashMap<String, Double>();
+ // Pattern p = Pattern.compile("[0-9]*");
+ String token;
+
if (i == 0) {
- if (word_probs.containsKey(sentence.get(1))) {
- available_pos = word_probs.get(sentence.get(1)); // here we get available states of the
- // first observation
- } else {
- // TODO ADD UNKNOWN WORDS HANDLER
- System.err.println("UNKNOWN");
- available_pos = word_probs.get("Apache"); // just for test purposes
+ // lookup for the non-capitalized variant of the word for the first word in a sentence and
+ // weight by relative frequencies of the corresponding forms and sum them
+ token = sentence.get(1);
+ String non_cap = token.toLowerCase();
+ /* Matcher m = p.matcher(token);
+ boolean b = m.matches();
+
+ if (b) {
+ System.out.println(token);
+ cardinals+=1;
+ available_pos = word_probs.get("@card");
+ //available_pos.put("CARD", 1.00);
+ }
+ else */
+ if (word_probs.containsKey(token)| word_probs.containsKey(non_cap)) {
+ if (ModelGeneration.capitalized(sentence.get(1)) & word_probs.containsKey(sentence.get(1))){
+ available_pos = word_probs.get(sentence.get(1)); // here we get available states of the
+ } else{
+ // if a lexicon contains a non-capitalized variant of a word
+ if (word_probs.containsKey(non_cap)) {
+ available_pos = word_probs.get(non_cap);
+ }}
+
+ } else
+ // 2. smoothed suffix- the strategy described in (Brants, 2000)
+ {
+ Map<String, Map<String, Double>> suffix_tree_local;
+ // if a word is capitalized ...
+ if (ModelGeneration.capitalized(sentence.get(1))){
+ suffix_tree_local = suffix_tree_cap;
+ } else {
+ suffix_tree_local = suffix_tree;
+ }
+
+ char [] unknown = sentence.get(1).toCharArray();
+ for (int j=0;j<unknown.length; j++){
+ // get the longest suffix distribution from the suffix tree
+ String suffix = sentence.get(1).substring(j, unknown.length);
+ if(suffix_tree_local.containsKey(suffix)){
+ // get available POS with corresponding counts for the longest suffix
+ Map available_pos_zwischen =suffix_tree_local.get(suffix);
+ // smoothing by successive abstraction for the probabilities of the longest suffix,
+ for(int suf=j+1; suf<unknown.length;suf++){
+ String subsuffix = sentence.get(1).substring(suf, unknown.length);
+ Map pos = new HashMap();
+ if(suffix_tree_local.containsKey(subsuffix)){
+ pos = suffix_tree_local.get(subsuffix);
+ Iterator posValuePairs = pos.entrySet().iterator();
+ while(posValuePairs.hasNext()){
+ Map.Entry<String, Double> entry = (Map.Entry<String, Double>) posValuePairs.next();
+ Object key = entry.getKey();
+ Double value = (Double) entry.getValue();
+ if (available_pos_zwischen.containsKey(key)) {
+ double zwischen_prob = (value + theta*(Double)available_pos_zwischen.get(key))/(1+theta);
+ available_pos_zwischen.put(key, zwischen_prob);
+ }/* else {
+ available_pos_zwischen.put(key, value);
+ }*/
+ }
+ } else {
+ Iterator posValuePairs2 = available_pos_zwischen.entrySet().iterator();
+ while(posValuePairs2.hasNext()){
+ Map.Entry<String, Double> entry = (Map.Entry<String, Double>) posValuePairs2.next();
+ Object key = entry.getKey();
+ Double value = (Double) entry.getValue();
+ // smooth suffix probability P(suffix|tag)
+ double zwischen_prob = (0 + theta*value)/(1+theta);
+ pos.put(key, zwischen_prob);
+
+ } available_pos_zwischen = pos;
+ }
+
+ }
+ available_pos = available_pos_zwischen;
+ break;
+ }
+ //
+ else if (j==unknown.length-1){
+ available_pos = word_probs.get("Clinton");
+ }
+ }
}
all.putAll(init_probs(END_OF_SENT_TAG, available_pos));
continue; // go over to the next token
}
- String token = sentence.get(i);
- // System.out.println("current word: "+token);
- Map<String, Double> possible_pos = new HashMap<String, Double>();
- if (word_probs.containsKey(token)) {
- possible_pos = word_probs.get(token); // get possible POS of the current word, otherwise
- // iterate over all, or limited set
- } else {
- possible_pos = word_probs.get("Apache"); // just for testing
- }
- // System.out.println("available POSs of the current token: "
- // +possible_pos);
-
+ token = sentence.get(i);
+
Map<String, List> m = new HashMap<String, List>(); // saves paths to the
// next token
/** ********************************************************* */
/** INDUCTION (~forward algorithm) * */
/** ********************************************************* */
- /**
- * At INDUCTION step the algorithm looks at the total and local possibilities of the next
+ /* At INDUCTION step the algorithm looks at the total and local possibilities of the next
* state(=tag), given a current observation (=token) If a token is known, we limit the coming
* tags by only possible ones for this token
*/
Map<String, Double> possible_pos_next = new HashMap<String, Double>(); // possible pos of the
// next token
+
+ /* Matcher m2 = p.matcher(token);
+ boolean b = m2.matches();
+
+ if (b) {
+ cardinals+=1;
+ possible_pos_next = word_probs.get("@card");
+ // possible_pos_next.put("CARD", 1.00);
+ }
+ else */
if (word_probs.containsKey(sentence.get(i + 1))) { // if the next token is known
- // System.out.println("next token is: "+sentence.get(i+1)+" and it is in the vocabulary");
possible_pos_next = word_probs.get(sentence.get(i + 1)); // get possible POS of the next
- // word, otherwise iterate over
- // all, or limited set
- } else {
- // TODO ADD UNKNOWN WORDS HANDLER
- // System.err.println("UNKNOWN NEXT WORD");
- possible_pos_next = word_probs.get("Apache"); // just for test purposes
+
+ } else
+ {
+ Map<String, Map<String, Double>> suffix_tree_local;
+ // if a word is capitalized ...
+ if (ModelGeneration.capitalized(sentence.get(i+1))){
+ suffix_tree_local = suffix_tree_cap;
+ } else {
+ suffix_tree_local = suffix_tree;
+ }
+
+ char [] unknown = sentence.get(i+1).toCharArray();
+ for (int j=0;j<unknown.length; j++){
+ // get the longest suffix distribution from the suffix tree
+ String suffix = sentence.get(i+1).substring(j, unknown.length);
+ if(suffix_tree_local.containsKey(suffix)){
+ // get available POS with corresponding counts for the longest suffix
+ Map available_pos_zwischen =suffix_tree_local.get(suffix);
+ //
+ for(int suf=j+1; suf<unknown.length;suf++){
+ String subsuffix = sentence.get(i+1).substring(suf, unknown.length);
+ Map pos = new HashMap();
+ if(suffix_tree_local.containsKey(subsuffix)){
+ pos = suffix_tree_local.get(subsuffix);
+ Iterator posValuePairs = pos.entrySet().iterator(); // iterate over words
+ while(posValuePairs.hasNext()){
+ Map.Entry<String, Double> entry = (Map.Entry<String, Double>) posValuePairs.next();
+ Object key = entry.getKey();
+ Double value = (Double) entry.getValue();
+ if (available_pos_zwischen.containsKey(key)) {
+ // smooth suffix probability P(suffix|tag)
+ double zwischen_prob = (value + theta*(Double)available_pos_zwischen.get(key))/(1+theta);
+ available_pos_zwischen.put(key, zwischen_prob);
+ }/* else {
+ available_pos_zwischen.put(key, value);
+ }*/
+ }
+ } else {
+ Iterator posValuePairs2 = available_pos_zwischen.entrySet().iterator(); // iterate over words
+ while(posValuePairs2.hasNext()){
+ Map.Entry<String, Double> entry = (Map.Entry<String, Double>) posValuePairs2.next();
+ Object key = entry.getKey();
+ Double value = (Double) entry.getValue();
+ // smooth suffix probability P(suffix|tag)
+ double zwischen_prob = (0 + theta*value)/(1+theta);
+ pos.put(key, zwischen_prob);
+
+ } available_pos_zwischen = pos;
+ }
+
+ }
+ possible_pos_next = available_pos_zwischen;
+ break;
+ }
+ else if (j==unknown.length-1){
+ possible_pos_next = word_probs.get("Clinton");
+ }
+ }
}
- // System.out.println("possible POSs of the next token: "
- // +possible_pos_next);
+
Iterator keyValuePairs_next = possible_pos_next.entrySet().iterator();
for (int u = 0; u < possible_pos_next.size(); u++) // for every possible tag of the next
// token, if the token is known..
- // otherwise - go through all available
- // POSs
{
- Map.Entry entry_next = (Map.Entry) keyValuePairs_next.next();
+ Map.Entry entry_next = (Map.Entry) keyValuePairs_next.next();
String key_next = (String) entry_next.getKey();
Double value_next = (Double) entry_next.getValue(); // get
- // P(next_token|this_next_state)
- // or P(w_i+1|t_i+i)
-
double total_prob = 0.0; // just for fun, for forward algorithm
List max_viterbi_path = new ArrayList<String>(); // viterbi path
double max_viterbi_prob = 0; // viterbi probability
- Iterator keyValuePairs = possible_pos.entrySet().iterator();
+
+ Iterator keyValuePairs = all.entrySet().iterator();
+
+
/** ********************************************************************************** */
/*
* calculates for the given next token which of the possible paths to the current token are
* more possible to end in the next token
*/
- for (int y = 0; y < possible_pos.size(); y++) // for every possible tag
+ for (int y = 0; y < all.size(); y++) // for every possible tag
// of this token (path
// till now)
{
Map.Entry entry = (Map.Entry) keyValuePairs.next();
- Object key = entry.getKey(); // get possible tag for the current
- // token
- Double value = (Double) entry.getValue(); // get its P(w|t)
-
- //
+ Object key = entry.getKey(); // get possible tag for the current token
List probs = all.get(key);
// Double prob_local = (Double) probs.get(0); // total_probability for
// forward algorihtm
List path_local = (List) probs.get(1); // path to that token
- Double vprob_local = (Double) probs.get(2); // get viterbi probability
- // for this token
+ Double vprob_local = (Double) probs.get(2); // get viterbi probability for this token
String ngram = null;
-
+ String ngram2 = null; // for smoothing of transition probs, at the moment for unknown grams only
+
/*
* The following 4 lines can be modified to get any other number of N-grams
*/
/* -- from here -- */
-
+ // um den ersten trigramm abzufangen
if (N == 3 && i == 1) {
ngram = path_local.get(path_local.size() - 1) + "_" + key_next;
- } // um den ersten trigramm abzufangen
- else if (N == 2) {
+
+ } else if (N == 2) {
+
ngram = path_local.get(path_local.size() - 1) + "_" + key_next;
+
} else if (N == 3 && i != 1) {
ngram = path_local.get(path_local.size() - 2) + "_"
+ path_local.get(path_local.size() - 1) + "_" + key_next;
+ ngram2 = path_local.get(path_local.size() - 1) + "_" + key_next;
+
} else {
System.err.println("at the moment only bi-and trigramms are supported");
}
@@ -262,19 +381,16 @@
// this step,
// i.e. for every possible pos of the next token we store all the
// possible paths to it
-
+ // System.out.println("m: "+m.entrySet().toString());
}
all = m;
-
}
-
+ // System.out.println("cardinals found: "+cardinals);
/** ****************************************************** */
/***********************************************************************************************
* Best sequence identification / Termination / Backtracking /
**********************************************************************************************/
- double total_prob = 0.0; // the overall probability of this sequence of
- // observations, answered by a forward algorithm
- // (braucht man eigentlich nich unbedingt?)
+
List max_viterbi_path = new ArrayList<String>(); // viterbi path
double max_viterbi_prob = 0.0; // viterbi probability
@@ -288,16 +404,12 @@
ArrayList value = (ArrayList) entry.getValue();
- // Double total_local = (Double) value.get(0);
List path_local = (List) value.get(1);
Double vprob_local = (Double) value.get(2);
if (j == 0) {
max_viterbi_prob = vprob_local;
}
-
- // total_prob += total_local;
- // System.out.println("P("+token+"|"+key+")*P("+bigram+")="+p);
if (vprob_local >= max_viterbi_prob) {
max_viterbi_path = path_local;
max_viterbi_prob = vprob_local;
@@ -305,10 +417,7 @@
}
List result = new ArrayList(3);
- // result.add(total_prob);
- // System.out.println("total_prob of this path"+total_prob);
result.add(max_viterbi_path);
-
result.add(max_viterbi_prob);
return max_viterbi_path;
}
Modified: incubator/uima/sandbox/trunk/Tagger/tagger.properties
URL: http://svn.apache.org/viewvc/incubator/uima/sandbox/trunk/Tagger/tagger.properties?rev=617123&r1=617122&r2=617123&view=diff
==============================================================================
--- incubator/uima/sandbox/trunk/Tagger/tagger.properties (original)
+++ incubator/uima/sandbox/trunk/Tagger/tagger.properties Thu Jan 31 05:00:08 2008
@@ -1,18 +1,23 @@
## This is the default tagger.properties file
-MODEL = brown_model_trigramm.dat
+MODEL = models/english/BrownModel.dat
+# MODEL = TigerKomplettModel_Mod.dat
+#MODEL = TuebaModel.dat
+# MODEL = TuebaModelKomplett_new.dat
+#MODEL = PennKomplett.sdat
+#MODEL = TigerTrainingModelKomplett.dat
+# MODEL = TuebaModel.dat
## uncomment the following two lines if training is desirable, and change the corpus directory destination path,
## e.g. T_CORPUS='brown' for all the files of the brown corpus which are in the 'brown/' -directory
-TRAINING = false
-# T_CORPUS = brown
-
-## change the following line to "true" for smoothing
-
-SMOOTHING = false
+# TRAINING = false
## N =2 or N= 3 are supported, default N=3
N = 3
-END_OF_SENT_TAG = .
\ No newline at end of file
+## not yet integrated into the program at this level
+END_OF_SENT_TAG = .
+
+## not yet integrated into the program at this level
+#MAPPING = false
\ No newline at end of file