Дерево в Java для хранения слов из текста

Question

У меня есть текстовый файл, где каждая строка - это путь словосочетаний word1 / word2 /.../ wordn, и я хочу запросить файл. Мне нужно построить дерево, в котором слова и каждая строка файла хранятся в виде пути, чтобы каждый раз, когда я ищу слово, я получал слово-узел и все пути, к которым принадлежит это слово. Мне было интересно, есть ли в Java встроенная библиотека, относящаяся к дереву / графику, или есть подходящая структура дерева, которую я мог бы использовать для текущей задачи. На самом деле, моя основная идея состоит в том, чтобы построить дерево так, чтобы я читал файл построчно и добавлял узлы и путь к этому дереву. Есть идеи-предложения?

Answer 1

То, что у вас есть, на самом деле совсем не дерево. Я бы использовал Map<String, List<String>> для хранения списка строк, который содержит каждое слово. Это использует O (n) памяти и имеет быстрый поиск. Пример кода:

import java.util.*;
import java.io.*;

public class WordNodes
{
    Map<String, List<String>> map = new HashMap<String, List<String>>();

    void readInputFile(String filename) throws IOException, FileNotFoundException
    {
        FileReader fileReader = new FileReader(filename);
        BufferedReader bufferedReader = new BufferedReader(fileReader);
        try
        {
            List<String> lines = new ArrayList<String>();
            String line = null;
            while ((line = bufferedReader.readLine()) != null)
            {
                for (String word: line.split("/"))
                {
                    List<String> list = map.get(word);
                    if (list == null)
                    {
                        list = new ArrayList<String>();
                        map.put(word, list);
                    }
                    list.add(line);
                }
            }
        } finally {
            bufferedReader.close();
        }
    }

    void run() throws IOException, FileNotFoundException
    {
        readInputFile("file.txt");
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);

        try
        {
            while (true)
            {
                String word = bufferedReader.readLine();
                List<String> lines = map.get(word);
                if (lines == null)
                {
                    System.out.println("Word not found.");
                }
                else
                {
                    for (String line: lines)
                    {
                        System.out.println(line);
                    }
                }
            }
        } finally {
            bufferedReader.close();
        }
    }

    public static void main(String[] args) throws Exception
    {
        new WordNodes().run();
    }
}

Answer 2

Я бы построил класс, содержащий слово и набор строк, содержащих это слово.

При обходе строк файла сохраняйте карту (java.util.HashMap или java.util.TreeMap, в зависимости от того, как вам нужно ее использовать позже) со словами (строками) в качестве ключей и классом выше в качестве значений. Для каждого слова в строке найдите его в словаре и добавьте строку к его записи (или добавьте новую запись, если ее там еще нет).

Поиск строк, в которых встречается слово, - это простой поиск по карте после того, как вы отсканировали файл.

Answer 3

Я бы исследовал хранение файла в XML-документе и использование XPath для его поиска. Ксерсес - хорошее начало. Каждая часть файла (word1 /) будет узлом с последующими словами (word2) в качестве дочернего элемента.

Answer 4

Мой первый хотя и похож на Liedman, но немного отличается: вместо того, чтобы создавать новый класс для линий, просто используйте Set<String> (HashSet<String>) или List<String> (ArrayList<String>).