텍스트 선택 교차점 알고리즘

Question

여러 사용자가 HTML 문서의 여러 부분 (주로 텍스트)을 강조 표시 할 수있는 웹 사이트가 있습니다.

각 강조 표시는 시작, 문자 위치, 길이 및 사용자 ID로 표시됩니다.

가장 강조 표시된 섹션 (가장 겹친 섹션)을 찾아야하지만, 다른 사용자의 시작과 끝 위치가 같지 않을 수 있습니다. 이러한 기능을 구현하는 가장 좋은 방법은 무엇입니까? 바람직하게는 C#

Answer 1

모든 사용자의 시작과 끝 선택을 정렬 된 목록에 넣습니다. 목록의 맨 위에서 시작하여 발견 한 각 시작점에 대해 카운터를 증가 시키면 발견 한 각 종점에 대해 감소합니다. 카운터의 가장 높은 값은 가장 강조 표시된 텍스트/가장 겹쳐진 텍스트 섹션의 시작입니다. 목록의 다음 항목은 해당 선택 항목의 끝입니다.

Answer 2

데이터를 둑 알고리즘에 필요한 구조로 변환해야합니다. 시간이 더 있다면 아마 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 
}