Алгоритм пересечения выделения текста

Question

У меня есть веб-сайт, который позволяет нескольким пользователям выделять несколько частей HTML-документа (в основном текст).

Каждое выделение помечено началом, позицией символа, длиной и идентификатором пользователя.

Мне нужно выяснить наиболее выделенные разделы (наиболее перекрывающиеся разделы), однако разные пользователи могут иметь разные начальные и конечные позиции. Как лучше всего реализовать такую ​​функцию? желательно в с #

Answer 1

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

Answer 2

Это должно преобразовать ваши данные в структуру, необходимую для алгоритма dthorpe.Если бы у меня было больше времени, я мог бы, вероятно, дать Linq-ify остальным.

ОБНОВЛЕНИЕ: Хорошо, теперь завершено (если еще не проверено ....) ОБНОВЛЕНИЕ2: Теперь действительно проверено и работает!

// Existing data structure
class StartLen
{
    public int Start {get; set;}
    public int Len   {get; set;}
    public string UserId {get; set;}
}

// Needed data struct
class StartEnd
{
    public int Pos {get; set;}
    public bool IsStart {get; set;}
}

class Segment
{
    public int Start { get; set; }
    public int End { get; set; }
    public int Count { get; set; }
}    

int count = 0, lastStart = -1;   // next rev, I figure a way to get rid of these. 

 // this can't be a lambda, it has to be a real function
IEnumerable<StartEnd> SplitSelection(StartLen sl)
 {  
    yield return new StartEnd() {Pos = sl.Start, IsStart = true} ; 
    yield return new StartEnd() {Pos = sl.Start+sl.Len -1 , IsStart = false} ; 
 }

List<StartLen> startLen = new List<StartLen>();
// we fill it with data for testing
// pretending to be the real data
startLen.Add(new StartLen() { Start=10, Len=10, UserId="abc123" });
startLen.Add(new StartLen() { Start=15, Len=10, UserId="xyz321" });

 var mostSelected  =  
    startLen.SelectMany<StartLen, StartEnd>(SplitSelection) 
        .OrderBy(se=>se.Pos) 
        .Select(se=>
        { 
            if (se.IsStart) 
            { 
                lastStart = se.Pos; 
                count++; 
            } 
            else 
            { 
                count--; 
                if (lastStart > 0) 
                { 
                    var seg = new Segment  
                        { Start = lastStart, End = se.Pos, Count = count }; 
                    lastStart = -1; 
                    return seg;
                } 
            } 
            // Garbage, cuz I need to return something 
            return new Segment { Start = 0, End = 0, Count = -1 };  
        }) 
       .OrderByDescending(seg => seg.Count) 
       .First(); 

// mostSelected  holds Start & End positions
}