查找所有区间包含

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

试试这个：

Map<Interval, List<Interval>> mapContainments = new HashMap<>();

for(Interval interval : listIntervals) {
    List<Interval> containments = listIntervals.stream()
        .filter(i -> i != interval 
             && i.getLeft() <= interval.getLeft() 
             && i.getRight() >= interval.getRight())
        .collect(Collectors.toList());

    mapContainments.put(interval, containments);
}

mapContainers 将包含每个区间的所有包含。

Answer 2

刚抽出时间阅读您的算法基础。这是一个真正的 O(n*log(n)) 。但是，它只是试图确定当前间隔是否包含在任何先前间隔中（“...包含在其他间隔中。”）。

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

您会认识到算法上的注释只是跟踪遇到的 "the righmost endpoint"。没有跟踪较早的时间间隔。

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

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

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

查找所有区间包含

finding all interval containments

java

algorithm

intervals

information-extraction