Удалите перекрывающиеся числа из кортежа в python, чтобы ни у двух кортежей не было одинакового начального или конечного номера - PullRequest
Новая
       29

Удалите перекрывающиеся числа из кортежа в python, чтобы ни у двух кортежей не было одинакового начального или конечного номера

0 голосов
/ 27 апреля 2020

У меня есть список кортежей. Каждый кортеж состоит из строки и слова. Теперь каждый диктант в этом состоит из списка кортежей. Размер списка составляет около 8 000 записей.

Пример данных: 

dataset = [('made of iron oxide', {'entities': [(12, 16, 'PRODUCT'), (17, 20, 'PRODUCT'), (15, 24, 'PRODUCT'), (12, 19, 'PRODUCT')]}),('made of ferric oxide', {'entities': [(10, 15, 'PRODUCT'), (12, 15, 'PRODUCT'), (624, 651, 'PRODUCT'), (1937, 1956, 'PRODUCT')]})]

Отсюда ожидается вывод: 

dataset = [('made of iron oxide', {'entities': [(17, 20, 'PRODUCT'), (15, 24, 'PRODUCT'), (12, 19, 'PRODUCT')]}), ('made of ferric oxide', {'entities': [(10, 15, 'PRODUCT'), (624, 651, 'PRODUCT'), (1937, 1956, 'PRODUCT')]})]

Note: (12, 19 «ПРОДУКТ») сохраняется в выходных данных, поскольку разница между начальным и конечным числом больше, чем (12, 16, «ПРОДУКТ»). PRODUCT является просто меткой и несущественным.

Эти числа являются индексами предложений, чей индекс entities отображается. Случайные предложения были помещены в пример, так как он несущественный, и операция должна выполняться только по условию entities. Я хочу удалить перекрывающиеся числа в моем списке и сохранить только те значения индекса entities, которые имеют наибольшую длину, то есть any value of entities cannot have the same starting or end number.

1 Ответ

0 голосов
/ 05 мая 2020 
class Solution(object): #Ref. https://www.geeksforgeeks.org/merging-intervals/
   def merge(self, intervals):
      """
      :type intervals: List[Interval]
      :rtype: List[Interval]
      """
      if len(intervals) == 0:
         return []
      self.quicksort(intervals,0,len(intervals)-1)
      #for i in intervals:
         #print(i.start, i.end)
      stack = []
      stack.append(intervals[0])
      for i in range(1,len(intervals)):
         last_element= stack[len(stack)-1]
         if last_element[1] >= intervals[i][0]:
            last_element[1] = max(intervals[i][1],last_element[1])
            stack.pop(len(stack)-1)
            stack.append(last_element)
         else:
            stack.append(intervals[i])
      return stack
   def partition(self,array,start,end):
      pivot_index = start
      for i in range(start,end):
         if array[i][0]<=array[end][0]:
            array[i],array[pivot_index] =array[pivot_index],array[i]
            pivot_index+=1
      array[end],array[pivot_index] =array[pivot_index],array[end]
      return pivot_index
   def quicksort(self,array,start,end):
      if start<end:
         partition_index = self.partition(array,start,end)
         self.quicksort(array,start,partition_index-1)
         self.quicksort(array, partition_index + 1, end)

for i in range(len(dataset)): #Your Solution
    arr1 = []
    for item in dataset[i][1]['entities']:
        arr1.append([item[0],item[1]])
    ob1 = Solution()
    arr2 = ob1.merge(arr1)
    arr3=[]
    for item in arr2:
        arr3.append((item[0],item[1], 'PRODUCT'))
    dataset[i][1]['entities'] = arr3
...