인덱서

웹 검색에서 인덱스는 검색어를 바탕으로 관련 페이지를 찾을 수 있게 하는 자료구조입니다. 

 

자료구조 선택

인덱스의 가장 기본 연산은 조회입니다. 특히 검색어를 조회하여 검색어를 포함한 모든 페이지를 찾는 능력이 필요합니다.

 

가장 단순한 구현은 페이지의 컬렉션입니다. 검색어가 주어지면 페이지 내용을 반복 조사하여 검색어를 포함한 페이지를 선택합니다. 하지만 실행시간은 모든 페이지의 전체 단어 수에 비례하며 매우 느립니다.

 

이보다 좀 더 나은 대안은 맵입니다. 이 자료구조는 키-값 쌍의 컬렉션을 나타내며, 키와 키에 해당하는 값를 찾는 빠른 방법을 제공합니다.

 

Map 인터페이스에서 가장 중요한 메서드는 다음과 같습니다. HashMap/ TreeMap 클래스

-get(key) 이 메서드는 키를 조사하여 관련된 값을 반환합니다.

-put(key, value) 이 메서드는 Map에 새로운 키-값 쌍을 추가하거나 맵에 이미 키가 있으면 key와 관련된 값을 대체합니다.

 

집합이 수행해야 하는 연산을 정의한 Set 인터페이스를 제공합니다. 이 인터페이스는 실제 교집합 연산을 제공하지 않지만, 교집합 연산과 다른 집합 연산을 효율적으로 구현할 수 있는 메서드를 제공합니다. HashSet/ TreeSet 클래스

-add(element)

이 메서드는 집합에 요소를 추가합니다. 동일한 요소가 집합에 이미 있다면 아무런 효과가 없습니다. 

-contains(element)

이 메서드는 주어진 요소가 집합에 포함되어 있는지 확인합니다.

 

package com.allendowney.thinkdast;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import org.jsoup.nodes.Node;
import org.jsoup.nodes.TextNode;
import org.jsoup.select.Elements;


/**
 * Encapsulates a map from search term to frequency (count).
 *
 * @author downey
 *
 */
public class TermCounter {

   private Map<String, Integer> map;
   private String label;

   public TermCounter(String label) {
      this.label = label;
      this.map = new HashMap<String, Integer>();
   }

   public String getLabel() {
      return label;
   }

   /**
    * Returns the total of all counts.
    *
    * @return
    */
   public int size() {
      int total = 0;
      for (Integer value: map.values()) {
         total += value;
      }
      return total;
   }

   /**
    * Takes a collection of Elements and counts their words.
    *
    * @param paragraphs
    */
   public void processElements(Elements paragraphs) {
      for (Node node: paragraphs) {
         processTree(node);
      }
   }

   /**
    * Finds TextNodes in a DOM tree and counts their words.
    *
    * @param root
    */
   public void processTree(Node root) {
      // NOTE: we could use select to find the TextNodes, but since
      // we already have a tree iterator, let's use it.
      for (Node node: new WikiNodeIterable(root)) {
         if (node instanceof TextNode) {
            processText(((TextNode) node).text());
         }
      }
   }

   /**
    * Splits `text` into words and counts them.
    *
    * @param text  The text to process.
    */
   public void processText(String text) {
      // replace punctuation with spaces, convert to lower case, and split on whitespace
      String[] array = text.replaceAll("\\pP", " ").
                          toLowerCase().
                          split("\\s+");
      
      for (int i=0; i<array.length; i++) {
         String term = array[i];
         incrementTermCount(term);
      }
   }

   /**
    * Increments the counter associated with `term`.
    *
    * @param term
    */
   public void incrementTermCount(String term) {
      // System.out.println(term);
      put(term, get(term) + 1);
   }

   /**
    * Adds a term to the map with a given count.
    *
    * @param term
    * @param count
    */
   public void put(String term, int count) {
      map.put(term, count);
   }

   /**
    * Returns the count associated with this term, or 0 if it is unseen.
    *
    * @param term
    * @return
    */
   public Integer get(String term) {
      Integer count = map.get(term);
      return count == null ? 0 : count;
   }

   /**
    * Returns the set of terms that have been counted.
    *
    * @return
    */
   public Set<String> keySet() {
      return map.keySet();
   }

   /**
    * Print the terms and their counts in arbitrary order.
    */
   public void printCounts() {
      for (String key: keySet()) {
         Integer count = get(key);
         System.out.println(key + ", " + count);
      }
      System.out.println("Total of all counts = " + size());
   }

   /**
    * @param args
    * @throws IOException
    */
   public static void main(String[] args) throws IOException {
      String url = "https://en.wikipedia.org/wiki/Java_(programming_language)";

      WikiFetcher wf = new WikiFetcher();
      Elements paragraphs = wf.fetchWikipedia(url);

      TermCounter counter = new TermCounter(url.toString());
      counter.processElements(paragraphs);
      counter.printCounts();
   }
}

package com.allendowney.thinkdast;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;

import org.jsoup.select.Elements;

/**
 * Encapsulates a map from search term to set of TermCounter.
 *
 * @author downey
 *
 */
public class Index {

    private Map<String, Set<TermCounter>> index = new HashMap<String, Set<TermCounter>>();

    /**
     * Adds a TermCounter to the set associated with `term`.
     *
     * @param term
     * @param tc
     */
    public void add(String term, TermCounter tc) {
        Set<TermCounter> set = get(term);

        // if we're seeing a term for the first time, make a new Set
        if (set == null) {
            set = new HashSet<TermCounter>();
            index.put(term, set);
        }
        // otherwise we can modify an existing Set
        set.add(tc);
    }

    /**
     * Looks up a search term and returns a set of TermCounters.
     *
     * @param term
     * @return
     */
    public Set<TermCounter> get(String term) {
        return index.get(term);
    }

   /**
    * Prints the contents of the index.
    */
   public void printIndex() {
      // loop through the search terms
      for (String term: keySet()) {
         System.out.println(term);
         
         // for each term, print the pages where it appears
         Set<TermCounter> tcs = get(term);
         for (TermCounter tc: tcs) {
            Integer count = tc.get(term);
            System.out.println("    " + tc.getLabel() + " " + count);
         }
      }
   }

   /**
    * Returns the set of terms that have been indexed.
    * 
    * @return
    */
   public Set<String> keySet() {
      return index.keySet();
   }

   /**
    * Add a page to the index.
    *
    * @param url         URL of the page.
    * @param paragraphs  Collection of elements that should be indexed.
    */
   public void indexPage(String url, Elements paragraphs) {
      //여기가 해결해야 될 부분이었다.
      // make a TermCounter and count the terms in the paragraphs
      TermCounter tc = new TermCounter(url);
      tc.processElements(paragraphs);
      
      // for each term in the TermCounter, add the TermCounter to the index
      for (String term: tc.keySet()) {
         add(term, tc);
      }
   }

   /**
    * @param args
    * @throws IOException 
    */
   public static void main(String[] args) throws IOException {
      
      WikiFetcher wf = new WikiFetcher();
      Index indexer = new Index();

      String url = "https://en.wikipedia.org/wiki/Java_(programming_language)";
      Elements paragraphs = wf.fetchWikipedia(url);
      indexer.indexPage(url, paragraphs);
      
      url = "https://en.wikipedia.org/wiki/Programming_language";
      paragraphs = wf.fetchWikipedia(url);
      indexer.indexPage(url, paragraphs);
      
      indexer.printIndex();
   }
}