Статьи

Мини поисковая система — только основы, используя Neo4j, Crawler4j, Graphstream и Encog

Продолжая к главе 4 « Programming Collection Intelligence» (PCI), которая реализует поисковую систему.

Возможно, я откусила немного больше, чем должна была сделать в одном упражнении. Я решил, что вместо использования обычной конструкции реляционной базы данных, использованной в книге, я всегда хотел взглянуть на Neo4J, поэтому сейчас самое время. Проще говоря, это не обязательно идеальный вариант использования для графа дБ, но насколько трудно может быть убить 3 птицы одним камнем.

Работая над учебниками, пытаясь перезагрузить мой SQL Server, мышление Oracle заняло немного больше времени, чем ожидалось, но, к счастью, вокруг Neo4j есть несколько замечательных ресурсов.

Просто пара:

Поскольку я просто хотел выполнить это как небольшое упражнение, я решил использовать реализацию в памяти, а не запускать ее как службу на моей машине. Оглядываясь назад, это, вероятно, было ошибкой, и инструменты и веб-интерфейс помогли бы мне быстрее визуализировать мой граф данных.

Поскольку у вас может быть только 1 доступный для записи экземпляр реализации в памяти, я создал небольшую фабрику с двумя блокировками для создания и очистки БД.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package net.briandupreez.pci.chapter4;
 
import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.factory.GraphDatabaseFactory;
import org.neo4j.kernel.impl.util.FileUtils;
 
import java.io.File;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
 
public class CreateDBFactory {
 
    private static GraphDatabaseService graphDb = null;
    public static final String RESOURCES_CRAWL_DB = "resources/crawl/db";
 
    public static GraphDatabaseService createInMemoryDB() {
        if (null == graphDb) {
            synchronized (GraphDatabaseService.class) {
                if (null == graphDb) {
                    final Map<String, String> config = new HashMap<>();
                    config.put("neostore.nodestore.db.mapped_memory", "50M");
                    config.put("string_block_size", "60");
                    config.put("array_block_size", "300");
                    graphDb = new GraphDatabaseFactory()
                            .newEmbeddedDatabaseBuilder(RESOURCES_CRAWL_DB)
                            .setConfig(config)
                            .newGraphDatabase();
 
                    registerShutdownHook(graphDb);
                }
            }
        }
        return graphDb;
    }
 
    private static void registerShutdownHook(final GraphDatabaseService graphDb) {
        Runtime.getRuntime().addShutdownHook(new Thread() {
            @Override
            public void run() {
                graphDb.shutdown();
            }
        });
    }
 
 
    public static void clearDb() {
        try {
            if(graphDb != null){
                graphDb.shutdown();
                graphDb = null;
            }
            FileUtils.deleteRecursively(new File(RESOURCES_CRAWL_DB));
        } catch (final IOException e) {
            throw new RuntimeException(e);
        }
    }
 
}

Затем с помощью Crawler4j создал график всех URL-адресов, начиная с моего блога, их отношений с другими URL-адресами и всех слов и индексов слов, содержащихся в этих URL-адресах.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package net.briandupreez.pci.chapter4;
 
 
import edu.uci.ics.crawler4j.crawler.Page;
import edu.uci.ics.crawler4j.crawler.WebCrawler;
import edu.uci.ics.crawler4j.parser.HtmlParseData;
import edu.uci.ics.crawler4j.url.WebURL;
import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.Transaction;
import org.neo4j.graphdb.index.Index;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Neo4JWebCrawler extends WebCrawler {
 
 
    private final GraphDatabaseService graphDb;
 
 
    /**
     * Constructor.
     */
    public Neo4JWebCrawler() {
        this.graphDb = CreateDBFactory.createInMemoryDB();
    }
 
 
    @Override
    public boolean shouldVisit(final WebURL url) {
        final String href = url.getURL().toLowerCase();
        return !NodeConstants.FILTERS.matcher(href).matches();
    }
 
    /**
     * This function is called when a page is fetched and ready
     * to be processed by your program.
     */
    @Override
    public void visit(final Page page) {
 
        final String url = page.getWebURL().getURL();
        System.out.println("URL: " + url);
 
        final Index<Node> nodeIndex = graphDb.index().forNodes(NodeConstants.PAGE_INDEX);
 
        if (page.getParseData() instanceof HtmlParseData) {
            HtmlParseData htmlParseData = (HtmlParseData) page.getParseData();
            String text = htmlParseData.getText();
            //String html = htmlParseData.getHtml();
            List<WebURL> links = htmlParseData.getOutgoingUrls();
            Transaction tx = graphDb.beginTx();
            try {
 
                final Node pageNode = graphDb.createNode();
                pageNode.setProperty(NodeConstants.URL, url);
                nodeIndex.add(pageNode, NodeConstants.URL, url);
 
                //get all the words
                final List<String> words = cleanAndSplitString(text);
                int index = 0;
                for (final String word : words) {
                    final Node wordNode = graphDb.createNode();
                    wordNode.setProperty(NodeConstants.WORD, word);
                    wordNode.setProperty(NodeConstants.INDEX, index++);
                    final Relationship relationship = pageNode.createRelationshipTo(wordNode, RelationshipTypes.CONTAINS);
                    relationship.setProperty(NodeConstants.SOURCE, url);
                }
 
                for (final WebURL webURL : links) {
                    System.out.println("Linking to " + webURL);
                    final Node linkNode = graphDb.createNode();
                    linkNode.setProperty(NodeConstants.URL, webURL.getURL());
                    final Relationship relationship = pageNode.createRelationshipTo(linkNode, RelationshipTypes.LINK_TO);
                    relationship.setProperty(NodeConstants.SOURCE, url);
                    relationship.setProperty(NodeConstants.DESTINATION, webURL.getURL());
                }
 
                tx.success();
            } finally {
                tx.finish();
            }
 
        }
    }
 
 
    private static List<String> cleanAndSplitString(final String input) {
        if (input != null) {
            final String[] dic = input.toLowerCase().replaceAll("\\p{Punct}", "").replaceAll("\\p{Digit}", "").split("\\s+");
            return Arrays.asList(dic);
        }
        return new ArrayList<>();
    }
 
}

После того, как данные были собраны, я мог запросить их и выполнить функции поисковой системы. Для этого я решил использовать Java-фьючерсы, так как это была еще одна вещь, о которой я только читал и еще не реализовал. В моей повседневной рабочей среде мы используем менеджеров работы Weblogic / CommonJ на сервере приложений для выполнения той же задачи.

01
02
03
04
05
06
07
08
09
10
final ExecutorService executorService = Executors.newFixedThreadPool(4);
final String[] searchTerms = {"java", "spring"};
 
List<Callable<TaskResponse>> tasks = new ArrayList<>();
tasks.add(new WordFrequencyTask(searchTerms));
tasks.add(new DocumentLocationTask(searchTerms));
tasks.add(new PageRankTask(searchTerms));
tasks.add(new NeuralNetworkTask(searchTerms));
 
final List<Future<TaskResponse>> results = executorService.invokeAll(tasks);

Затем я приступил к созданию задачи для каждого из следующих подсчетов: подсчета частоты слова, местоположения документа, рейтинга страницы и нейронной сети (с поддельными данными ввода / обучения) для ранжирования страниц, возвращаемых на основе критериев поиска. Весь код находится в моем публичном репозитории на блоге github.

Отказ от ответственности: Задача Neural Network либо не имела достаточного количества данных для эффективной работы, либо я неправильно ввел нормализацию данных, так что в настоящее время она не очень полезна, я вернусь к ней, когда завершу путешествие по PCI книга.

Единственной задачей, которой стоит поделиться, был Page Rank, я быстро прочитал некоторые теории для этого, решил, что я не настолько умен, и пошел искать библиотеку, в которой это реализовано. Я открыл для себя Graphstream замечательный проект с открытым исходным кодом, который делает ВЕСЬ БОЛЬШЕ, чем просто PageRank, посмотрите их видео.

Из этого было тогда просто реализовать мою задачу PageRank этого упражнения.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package net.briandupreez.pci.chapter4.tasks;
 
import net.briandupreez.pci.chapter4.NodeConstants;
import net.briandupreez.pci.chapter4.NormalizationFunctions;
import org.graphstream.algorithm.PageRank;
import org.graphstream.graph.Graph;
import org.graphstream.graph.implementations.SingleGraph;
import org.neo4j.cypher.javacompat.ExecutionEngine;
import org.neo4j.cypher.javacompat.ExecutionResult;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.Callable;
 
public class PageRankTask extends SearchTask implements Callable<TaskResponse> {
 
    public PageRankTask(final String... terms) {
        super(terms);
    }
 
    @Override
    protected ExecutionResult executeQuery(final String... words) {
        final ExecutionEngine engine = new ExecutionEngine(graphDb);
        final StringBuilder bob = new StringBuilder("START page=node(*) MATCH (page)-[:CONTAINS]->words ");
        bob.append(", (page)-[:LINK_TO]->related ");
        bob.append("WHERE words.word in [");
        bob.append(formatArray(words));
        bob.append("] ");
        bob.append("RETURN DISTINCT page, related");
 
        return engine.execute(bob.toString());
    }
 
    public TaskResponse call() {
        final ExecutionResult result = executeQuery(searchTerms);
        final Map<String, Double> returnMap = convertToUrlTotalWords(result);
 
        final TaskResponse response = new TaskResponse();
        response.taskClazz = this.getClass();
        response.resultMap = NormalizationFunctions.normalizeMap(returnMap, true);
        return response;
    }
 
    private Map<String, Double> convertToUrlTotalWords(final ExecutionResult result) {
        final Map<String, Double> uniqueUrls = new HashMap<>();
 
        final Graph g = new SingleGraph("rank", false, true);
        final Iterator<Node> pageIterator = result.columnAs("related");
 
        while (pageIterator.hasNext()) {
            final Node node = pageIterator.next();
            final Iterator<Relationship> relationshipIterator = node.getRelationships().iterator();
            while (relationshipIterator.hasNext()) {
 
                final Relationship relationship = relationshipIterator.next();
                final String source = relationship.getProperty(NodeConstants.SOURCE).toString();
                uniqueUrls.put(source, 0.0);
                final String destination = relationship.getProperty(NodeConstants.DESTINATION).toString();
                g.addEdge(String.valueOf(node.getId()), source, destination, true);
 
            }
        }
 
 
        computeAndSetPageRankScores(uniqueUrls, g);
        return uniqueUrls;
    }
 
    /**
     * Compute score
     *
     * @param uniqueUrls urls
     * @param graph      the graph of all links
     */
    private void computeAndSetPageRankScores(final Map<String, Double> uniqueUrls, final Graph graph) {
        final PageRank pr = new PageRank();
        pr.init(graph);
        pr.compute();
 
        for (final Map.Entry<String, Double> entry : uniqueUrls.entrySet()) {
            final double score = 100 * pr.getRank(graph.getNode(entry.getKey()));
            entry.setValue(score);
        }
    }
 
 
}

Между всем этим я нашел отличную реализацию сортировки карты по значениям в Stackoverflow.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package net.briandupreez.pci.chapter4;
 
import java.util.*;
 
 
public class MapUtil {
 
    /**
     * Sort a map based on values.
     * The values must be Comparable.
     *
     * @param map       the map to be sorted
     * @param ascending in ascending order, or descending if false
     * @param <K>       key generic
     * @param <V>       value generic
     * @return sorted list
     */
    public static <K, V extends Comparable<? super V>> List<Map.Entry<K, V>> entriesSortedByValues(final Map<K, V> map, final boolean ascending) {
 
        final List<Map.Entry<K, V>> sortedEntries = new ArrayList<>(map.entrySet());
        Collections.sort(sortedEntries,
                new Comparator<Map.Entry<K, V>>() {
                    @Override
                    public int compare(final Map.Entry<K, V> e1, final Map.Entry<K, V> e2) {
                        if (ascending) {
                            return e1.getValue().compareTo(e2.getValue());
                        } else {
                            return e2.getValue().compareTo(e1.getValue());
                        }
                    }
                }
        );
 
        return sortedEntries;
    }
 
}

Зависимости Maven, используемые для реализации всего этого

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>14.0.1</version>
  </dependency>
  <dependency>
      <groupId>org.encog</groupId>
      <artifactId>encog-core</artifactId>
      <version>3.2.0-SNAPSHOT</version>
  </dependency>
  <dependency>
      <groupId>edu.uci.ics</groupId>
      <artifactId>crawler4j</artifactId>
      <version>3.5</version>
      <type>jar</type>
      <scope>compile</scope>
  </dependency>
  <dependency>
      <groupId>org.neo4j</groupId>
      <artifactId>neo4j</artifactId>
      <version>1.9</version>
  </dependency>
  <dependency>
      <groupId>org.graphstream</groupId>
      <artifactId>gs-algo</artifactId>
      <version>1.1.2</version>
  </dependency>

Теперь к главе 5 по PCI … Оптимизация.