<commit_before>/**
 *
 * APDPlat - Application Product Development Platform
 * Copyright (c) 2013, 杨尚川, <EMAIL>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

package org.apdplat.word.util;


import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 通用的双数组前缀树的Java实现
 * 用于快速检索 K V 对
 * An Implementation of Double-Array Trie: http://linux.thai.net/~thep/datrie/datrie.html
 * @author 杨尚川
 */
public class DoubleArrayGenericTrie{
    private static final Logger LOGGER = LoggerFactory.getLogger(DoubleArrayGenericTrie.class);
    private int size = 65000;

    public DoubleArrayGenericTrie(int size){
        this.size = size;
    }

    private static class Node {
        private int code;
        private int depth;
        private int left;
        private int right;
        private int value;

        @Override
        public String toString() {
            return "Node{" +
                    "code=" + code + "["+ (char)code + "]" +
                    ", depth=" + depth +
                    ", left=" + left +
                    ", right=" + right +
                    ", value=" + value +
                    '}';
        }
    };

    private int[] check;
    private int[] base;
    private boolean[] used;
    private int nextCheckPos;

    public DoubleArrayGenericTrie(){
        LOGGER.info("初始化双数组前缀树：" + this.getClass().getName());
    }

    private List<Node> toTree(Node parent, List<String> items, Map<String, Integer> map) {
        List<Node> siblings = new ArrayList<>();
        int prev = 0;

        for (int i = parent.left; i < parent.right; i++) {
            if (items.get(i).length() < parent.depth)
                continue;

            String item = items.get(i);

            int cur = 0;
            if (item.length() != parent.depth) {
                cur = (int) item.charAt(parent.depth);
            }

            if (cur != prev || siblings.isEmpty()) {
                Node node = new Node();
                node.depth = parent.depth + 1;
                node.code = cur;
                node.left = i;
                if(cur==0 || cur==item.charAt(item.length()-1)){
                    if(map.get(item)!=null) {
                        node.value = map.get(item);
                    }
                }
                if (!siblings.isEmpty()) {
                    siblings.get(siblings.size() - 1).right = i;
                }
                siblings.add(node);
            }

            prev = cur;
        }

        if (!siblings.isEmpty()) {
            siblings.get(siblings.size() - 1).right = parent.right;
            if(LOGGER.isDebugEnabled()) {
                LOGGER.debug("************************************************");
                LOGGER.debug("树信息：");
                siblings.forEach(s -> LOGGER.debug(s.toString()));
                LOGGER.debug("************************************************");
            }
        }
        return siblings;
    }

    private int toDoubleArray(List<Node> siblings, List<String> words, Map<String, Integer> map) {
        int begin = 0;
        int index = (siblings.get(0).code > nextCheckPos) ? siblings.get(0).code : nextCheckPos;
        boolean isFirst = true;

        outer: while (true) {
            index++;

            if (check[index] != 0) {
                continue;
            } else if (isFirst) {
                nextCheckPos = index;<commit_msg>不输出大数据集的调试信息<commit_after>/**
 *
 * APDPlat - Application Product Development Platform
 * Copyright (c) 2013, 杨尚川, <EMAIL>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

package org.apdplat.word.util;


import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 通用的双数组前缀树的Java实现
 * 用于快速检索 K V 对
 * An Implementation of Double-Array Trie: http://linux.thai.net/~thep/datrie/datrie.html
 * @author 杨尚川
 */
public class DoubleArrayGenericTrie{
    private static final Logger LOGGER = LoggerFactory.getLogger(DoubleArrayGenericTrie.class);
    private int size = 65000;

    public DoubleArrayGenericTrie(int size){
        this.size = size;
    }

    private static class Node {
        private int code;
        private int depth;
        private int left;
        private int right;
        private int value;

        @Override
        public String toString() {
            return "Node{" +
                    "code=" + code + "["+ (char)code + "]" +
                    ", depth=" + depth +
                    ", left=" + left +
                    ", right=" + right +
                    ", value=" + value +
                    '}';
        }
    };

    private int[] check;
    private int[] base;
    private boolean[] used;
    private int nextCheckPos;

    public DoubleArrayGenericTrie(){
        LOGGER.info("初始化双数组前缀树：" + this.getClass().getName());
    }

    private List<Node> toTree(Node parent, List<String> items, Map<String, Integer> map) {
        List<Node> siblings = new ArrayList<>();
        int prev = 0;

        for (int i = parent.left; i < parent.right; i++) {
            if (items.get(i).length() < parent.depth)
                continue;

            String item = items.get(i);

            int cur = 0;
            if (item.length() != parent.depth) {
                cur = (int) item.charAt(parent.depth);
            }

            if (cur != prev || siblings.isEmpty()) {
                Node node = new Node();
                node.depth = parent.depth + 1;
                node.code = cur;
                node.left = i;
                if(cur==0 || cur==item.charAt(item.length()-1)){
                    if(map.get(item)!=null) {
                        node.value = map.get(item);
                    }
                }
                if (!siblings.isEmpty()) {
                    siblings.get(siblings.size() - 1).right = i;
                }
                siblings.add(node);
            }

            prev = cur;
        }

        if (!siblings.isEmpty()) {
            siblings.get(siblings.size() - 1).right = parent.right;
            if(LOGGER.isDebugEnabled()) {
                if (items.size()<10) {
                    LOGGER.debug("************************************************");
                    LOGGER.debug("树信息：");
                    siblings.forEach(s -> LOGGER.debug(s.toString()));
                    LOGGER.debug("************************************************");
                }
            }
        }
        return siblings;
    }

    private int toDoubleArray(List<Node> siblings, List<String> words, Map<String, Integer> map) {
        int begin = 0;
        int index = (siblings.get(0).code > nextCheckPos) ? siblings.get(0).code : nextCheckPos;
        boolean isFirst = true;

        outer: while (true) {
            index++;

            if (check[index] != 0) {
                continue;
            } else if (isFirst) {
                nextCheckPos = index;
{'fraction_non_alphanumeric': 0.1366355587461115, 'fraction_numerical': 0.00574300071787509, 'mean_word_length': 1.8201754385964912, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3521920', 'n_tokens_mistral': 2399, 'n_tokens_neox': 2333, 'n_words': 647}