java - 查找所有区间包含

Question

给定一组区间(表示范围的整数对)我想找到所有区间包含关系。我使用它的应用程序是删除信息提取系统中的冗余项；给定一组提取的段，其中一些被分类为地址，如果我检测到间隔 [2,3] 和 [2,6] 都是地址(也许第一个是街道地址，但第二个包含邮政编码之前的所有内容)，那么我只需要包含间隔。

我在网上只能找到几个提到这个问题，我用的是稀疏的笔记here在 Java 中实现以下内容:

import static java.util.Collections.reverseOrder;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class IntervalContainmentDetector {
    private static class Interval {
        private final int left;
        private final int right;
        public Interval(int l, int r) {
            left = l;
            right = r;
        }
        public int getLeft() {
            return left;
        }
        public int getRight() {
            return right;
        }
        public String toString() {
            return "[" + left + "," + right + "]";
        }
    }

    public static void main(String[] args) {
        @SuppressWarnings("serial")
        List<Interval> intervals = new LinkedList<Interval>() {
            {
                add(new Interval(0, 4));
                add(new Interval(2, 3));
                add(new Interval(0, 6));
                add(new Interval(4, 9));
                add(new Interval(4, 9));
                add(new Interval(4, 5));
                add(new Interval(3, 4));
                add(new Interval(6, 9));
                add(new Interval(4, 4));
                add(new Interval(5, 7));
                add(new Interval(1, 2));
            }
        };

        findContainments(intervals);
    }

    // sort ascending on left, descending on right;
    private static final Comparator<Interval> INTERVAL_SORTER = Comparator
            .comparing(Interval::getLeft).thenComparing(
                    interval -> interval.getRight(), reverseOrder());

    private static void findContainments(List<Interval> intervals) {
        List<Interval> sorted = intervals.stream().sorted(INTERVAL_SORTER)
                .collect(Collectors.toList());
        System.out.println("sorted: " + sorted);
        while (!sorted.isEmpty()) {
            LinkedList<Interval> containers = new LinkedList<>();
            containers.add(sorted.remove(0));
            recurse(sorted, containers);
        }
    }

    private static void recurse(List<Interval> remainingList,
            LinkedList<Interval> inList) {
        if (remainingList.isEmpty())
            return;
        while (!remainingList.isEmpty()) {
            Interval thisElement = remainingList.get(0);
            if (thisElement.getRight() <= inList.getLast().getRight()) {
                printContainment(inList, thisElement);
                remainingList.remove(0);
                inList.addLast(thisElement);
                recurse(remainingList, inList);
                inList.removeLast();
            } else
                return;
        }
    }

    private static void printContainment(List<Interval> containerList,
            Interval containedElement) {
        System.out.println(containedElement + " is contained by "
                + containerList);
    }
}

“sorted”打印用于确定排序是否正常工作。上面的代码打印以下内容:

sorted: [[0,6], [0,4], [1,2], [2,3], [3,4], [4,9], [4,9], [4,5], [4,4], [5,7], [6,9]]
[0,4] is contained by [[0,6]]
[1,2] is contained by [[0,6], [0,4]]
[2,3] is contained by [[0,6], [0,4]]
[3,4] is contained by [[0,6], [0,4]]
[4,9] is contained by [[4,9]]
[4,5] is contained by [[4,9], [4,9]]
[4,4] is contained by [[4,9], [4,9], [4,5]]
[5,7] is contained by [[4,9], [4,9]]
[6,9] is contained by [[4,9], [4,9]]

它忽略了 [4,5] 包含在 [0,6] 中；如果我删除两个 [4,9] 对，那么算法将正常工作。

我不确定如何更新算法以在这种情况下正常工作(其中非包含区间包含包含区间，有效地阻止发现关系)。我现在意识到，我在上面提到的幻灯片(以及此 other class site)中看到的问题陈述是列出包含在任何其他区间内的区间，而不是列出所有包含关系。

如何更新此算法以正确找到所有区间包含？

Answer 1

刚抽出时间阅读您的算法基础知识。这是一个真正的 O(n*log(n)) 。然而，它只是试图识别当前区间是否包含在任何先前的区间中(“...包含在其他区间中。”)。

你尝试的是不同的。您打算列出所有包含关系。 原始算法没有涵盖这一点，这就是破坏 log(n) 减少并导致 O(n^2) 复杂度的原因。

您会认识到算法中的注释只是跟踪遇到的“最右边的端点”。不跟踪早期间隔。

目标的减少首先使复杂性降低的算法成为可能。

获取所有 包含迫使您处理区间的部分排序。 (这就是导致您的算法无法检测到某些包含的原因。)原始算法利用转换为间隔的总排序以获得“某些包含”属性。

对于精确包含，您需要遵守自然偏序，最终进行完整的 n*(n-1) 比较。 或者，您可以利用有关要检查的间隔之间的关系的知识，但这与首先运行算法的需要相矛盾。 所以我怀疑你会比 O(n^2) 更好地获得所有遏制。