Problema da Distância Documental

Motivação: Dados dois documentos, quão semelhantes eles são?

• Idênticos?
• Modificados ou relacionados (plágio, DNA…)

Como exemplo prático vamos brincar com o velho e o novo Testamento mas antes há-que introduzir algumas definições:

1. Palavra: sequência de caracteres alfanuméricos (por exemplo, a frase “666.6 é quase o número da besta” tem 8 palavras).
2. Frequência de palavras: Definimos a frequência de uma palavra , D(w) como o número de vezes que ela ocorre num documento D.
3. Distância Métrica: A distância métrica entre documentos é definida como o produto interno entre os vectores D1 e D2 que contêm as frequências de todas as palavras nos dois documentos. Matematicamente,
   D1 . D2 = ∑w[D1(w).D2(w)]          (1)
4. Ângulo Métrico: o ângulo entre os vectores D1 e D2 dá-nos uma indicação da sobreposição dos dois documentos. Matematicamente,
   θ(D1.D2) = arccos(D1.D2 / ||D1|| * ||D2||)          com   0 ≤ θ ≤ π/2. Um ângulo métrico de 0 significa que os dois documentos são idênticos enquanto que um ângulo métrico de π/2 indica-nos que não há palavras em comum.
5. Número de palavras em um Documento: a magnitude do vector D que contém frequências de palavras de todas as palavras no documento.. Matematicamente, N(D) = ||D|| = √(D.D)

No fundo, o que estamos a fazer aqui é calcular o produto interno entre dois vectores. Para uma melhor compreensão, ver Dot Product

Uma boa fonte para livros em formato txt é Gutenberg

Resumindo, para calcular a distância entre dois documentos,

     Para cada um dos dois ficheiros:

          - Ler o ficheiro

          - Fazer uma lista de palavras

          - Contar as frequências

          - Ordenar

     Uma vez obtidos os vectores D1 e D2:

          Calcular o ângulo θ

Vamos ver o código:

/**
 * @author Manuel Leiria
 *
 */
public class DocumentMatcher {
	private Map<String, Integer> mapWordFrequencyDoc1 = 
             new TreeMap<String, Integer>();
	private Map<String, Integer> mapWordFrequencyDoc2 = 
             new TreeMap<String, Integer>();

	/**
	 * @return the mapWordFrequencyDoc1
	 */
	public Map<String, Integer> getMapWordFrequencyDoc1() {
		return Collections.unmodifiableMap(mapWordFrequencyDoc1);
	}
	/**
	 * @return the mapWordFrequencyDoc2
	 */
	public Map<String, Integer> getMapWordFrequencyDoc2() {
		return Collections.unmodifiableMap(mapWordFrequencyDoc2);
	}
	/**
	 *
	 * @param file1
	 * @param file2
	 */
	public DocumentMatcher(final String file1, final String file2) {
		buildFrequencyMap(file1, mapWordFrequencyDoc1);
		buildFrequencyMap(file2, mapWordFrequencyDoc2);
		synchronizeWordMaps();
	}
	/**
	 * Constroi um Mapa na forma [palavra, num. de vezes que
         *  ela ocorre no documento]
	 * @param file
	 * @param mapWordFrequency
	 */
	private void buildFrequencyMap
             (final String file, Map<String, Integer> mapWordFrequency){
		try{
			Scanner input = new Scanner(new File(file));
			while(input.hasNextLine()){
			    final String line = input.nextLine();
			        StringTokenizer parser = 
                                 new StringTokenizer(line, ",.;:()-!?' ");
			    while(parser.hasMoreTokens()){
			        final String word = 
                                    parser.nextToken().toUpperCase();

				Integer listing = mapWordFrequency.get(word);
				if(listing == null){
				    listing = 1;
				}else{
				    listing += 1;
				}
				mapWordFrequency.put(word, listing);
			    }
			}
		input.close();
		}catch(IOException e){
			System.out.println(e);
		}
	}
	/**
	 * Adiciona as palavras que nao existem nos respectivos mapas
	 */
	private void synchronizeWordMaps(){
		for(final Map.Entry<String, Integer> entry : 
                  mapWordFrequencyDoc1.entrySet()){
		    if(!mapWordFrequencyDoc2.containsKey(entry.getKey())){
		      mapWordFrequencyDoc2.put(entry.getKey(), 0);
		    }
		}
		for(final Map.Entry<String, Integer> entry : 
                  mapWordFrequencyDoc2.entrySet()){
		    if(!mapWordFrequencyDoc1.containsKey(entry.getKey())){
		      mapWordFrequencyDoc1.put(entry.getKey(), 0);
		    }
		}
	}
	/**
	 *
	 * @return o angulo theta entre os dois documentos
	 * Um theta = 0 => documetos identicos
	 * Um theta = pi/2 => Nao ha palavras em comum
	 */
	public double getTheta(){
		double [] frequency1 = 
                  new double[mapWordFrequencyDoc1.size()];
		double [] frequency2 = 
                  new double[mapWordFrequencyDoc2.size()];
		int cnt = 0;
		for(final Map.Entry<String, Integer> entry : 
                  mapWordFrequencyDoc1.entrySet()){
			frequency1[cnt] = entry.getValue();
			cnt++;
		}
		cnt = 0;
		for(final Map.Entry<String, Integer> entry : 
                  mapWordFrequencyDoc2.entrySet()){
			frequency2[cnt] = entry.getValue();
			cnt++;
		}
		double theta = 0;
		for(int i=0,n=frequency1.length;i<n;i++){
			theta += frequency1[i]*frequency2[i];
		}
		return Math.acos(theta / 
                (getNorm(mapWordFrequencyDoc1) * 
                  getNorm(mapWordFrequencyDoc2)));
	}
	/**
	 * Calcula a norma de D(w)
	 * @param vector
	 * @return ||D(w)||
	 */
	private double getNorm(Map<String, Integer> vector ){
		double norm = 0.0;
		for(final Map.Entry<String, Integer> entry : 
                  vector.entrySet()){
			norm += Math.pow(entry.getValue(), 2);
		}
		return Math.sqrt(norm);
	}
	/**
	 * Escreve o resultado para um ficheiro
	 * @param file
	 * @param mapWordFrequency
	 */
	public void writeString(final String file, 
          final Map<String, Integer> mapWordFrequency){
		try {
			final PrintWriter output = new PrintWriter(file);
			for(final Map.Entry<String, Integer> entry : 
                          mapWordFrequency.entrySet()){
				output.println(entry);
			}
			output.close();
		} catch (FileNotFoundException e) {
			System.out.println(e);
		}
	}
}
public class TestDocumentMatcher {

	public static final String PATH =
		"/home/manuel/Documentos/Books/";
	public static final String IN_FILE_1 =
		"New_Testament.txt";
	public static final String IN_FILE_2 =
		"Old_Testament.txt";

	public static final String OUT_FILE_1 =
		"New_Testament.out";
	public static final String OUT_FILE_2 =
		"Old_Testament.out";
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long initTime = Calendar.getInstance().getTimeInMillis();
		DocumentMatcher dc =
			new DocumentMatcher(PATH + IN_FILE_1, 
                          PATH + IN_FILE_2);

		dc.writeString(PATH + OUT_FILE_1, 
                  dc.getMapWordFrequencyDoc1());
		dc.writeString(PATH + OUT_FILE_2, 
                  dc.getMapWordFrequencyDoc2());

		System.out.println("THETA-->" + dc.getTheta());
		System.out.println("Pi/2-->" + Math.PI/2);
		long elapsedTime =
			Calendar.getInstance().
                          getTimeInMillis() - initTime;
		System.out.println("TIME ELAPSED-->" + 
                  elapsedTime/1000 + " seconds");
	}
}
THETA-->0.2850240436473282
Pi/2-->1.5707963267948966
TIME ELAPSED-->1 seconds

---