Python 中的匹配重叠区间（字典）
Matching overlapping Intervals (Dictionary) in Python
所以，我试图通过 python 解决一些随机问题，但在逻辑上卡住了。这是问题所在：
我有多个视频及其 运行 时间或 运行ning 长度。现在，我想维护 2 个列表。 1 个列表如果 "synced"，另一个是 "non synced"。如果流的 运行 时间差小于或等于 2 秒，我们决定 "synced"。否则，它们不会同步。
如果我们有多个匹配的流，那么我们将采用匹配度最高的流 count/number.
我想出了一个非常 simple/slow 的方法来分割和配对这些文件。但是，当我得到不同的数据集时，我的逻辑失败了。
这是我写的:
from datetime import datetime
# same_streams_old = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:08.990644",
"Stream_3": "0:24:08.990644",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:12.118778",
"stream_6": "0:24:10.075066"
}
same_streams = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:12.118778",
"Stream_3": "0:23:11.057711",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:10.075066",
"Stream_6": "0:24:08.990644"
}
keys = []
values = []
final_synced_video_files = []
final_non_synced_video_files = []
def get_time_diff(episode_run_time, episode_time):
prev_episode_time = datetime.strptime(episode_run_time, '%H:%M:%S.%f')
current_episode_time = datetime.strptime(episode_time, '%H:%M:%S.%f')
time_diff = prev_episode_time - current_episode_time
if current_episode_time > prev_episode_time:
time_diff = current_episode_time - prev_episode_time
return float(time_diff.seconds)
for key, value in same_streams.items():
keys.append(key)
values.append(value)
for key in keys:
for _key in keys:
if key != _key:
diff = get_time_diff(same_streams[key], same_streams[_key])
if diff <= 1.5:
final_synced_video_files.append(key)
else:
pass
final_synced_video_files = list(set(final_synced_video_files))
final_non_synced_video_files = list(set(keys) - set(final_synced_video_files))
print("Synced Files : {0}".format(final_synced_video_files))
print("Non Synced Files : {0}".format(final_non_synced_video_files))
如您所见，匹配最多的流是 stream_1、stream_2、stream_3 和 stream_6。
我写的还没有比较最大计数。但是，在我处理这个问题时，我觉得这并不是真正有效的解决方法。有人有任何意见吗？
我尝试了一些关于重叠间隔的方法然后得到了这个：REPL LINK
但是，如果您 运行 同时查看 same_streams 词典，您会发现结果不是我想要达到的。任何帮助都会很棒。
编辑：
我需要获得彼此相差 2 秒的流。例如 ：
在 same_streams_old 中，期望的结果是流 1、2、3 和 6。但是，在字典 same_streams 中，期望的结果是流 2、4 和 5。
基本上，我需要查看哪些流可以 "muxed" 在一起，哪些不能混合。
好的，所以下面的打印例程可能有点乱，但请耐心等待，它们仅用于调试，完成后您可能不需要它们。我知道这是一个很长的答案，但请仔细阅读..
简答：
您的问题可能是因为当您从字符串转换为 datetime 时丢失了小数精度，后者将秒视为整数。但是，timedelta 对象有一个名为 total_seconds() 的方法，它确实提供亚秒级分辨率。有关详细信息，请参阅 this 或一般文档。只需将 get_time_diff() 的 return 语句更改为，
return float(time_diff.total_seconds())
长答案的动机：
我不确定你想用（非和）同步列表实现什么：你可能遇到流 a 同步的情况使用流 b，而流 c 与 d 同步，但 c 和 d not 与 a[=70= 同步] 和 b。他们都应该在你的 synced_list 中吗？根据你想对列表做什么，我会考虑使用下面描述的同步矩阵，而不是你的列表，因为它们会丢失很多信息。
长答案：
让我介绍一下同步矩阵的概念。它将完整描述您的哪些流相互同步：
THE SYNC MATRIX:
A symmetric matrix;
Cell (i,j) in the matrix is TRUE if, and only if, stream 'i' and 'j'
are in sync. Else, the cell value is FALSE.
Hence, the diagonal (.) is entirely TRUE because a
stream is always in sync with itself.
1 2 3 4
________
1 | . T T F
2 | . T F
3 | . F
4 | .
"T" is true, and "F" is false: obviously from the example drawing above, stream 1 is in sync with stream 2, but not in sync with stream 4.
创建这样一个同步矩阵对于您的示例来说非常简单：
def is_synced(key_1, key_2):
max_allowed_desync = 1.5
return max_allowed_desync > get_time_diff(same_streams[key_1], same_streams[key_2])
keys = same_streams.keys()
keys.sort() # VERY IMPORTANT, for the synced matrix to be constructed correctly; also make 's' uppercase for "stream_6" in OP.
# The complete matrix ..
full_sync_matrix = [[is_synced(k1,k2) for k2 in keys] for k1 in keys]
# We can optimize (memory usage) to only get the half matrix, since it's symmetric anyway; also excluding the diagonal.
half_sync_matrix = [[is_synced(k1,k2) for k2 in keys[curr+1:]] for curr,k1 in enumerate(keys)]
现在，让我们为 printing/displaying 同步矩阵实现两个函数：
# Print a HALFED sync matrix
def print_sync_half_matrix(sm):
string = ""
for i,row in enumerate(sm):
string += "\n" + " "*i*2
for col in row:
string += " " + ("T" if col else "F")
print(string)
# Print a COMPLETE sync_matrix
def print_sync_full_matrix(sm):
string = ""
for row in sm:
string += "\n"
for col in row:
string += " " + ("T" if col else "F")
print(string)
然后，对于您提供的数据集，我得到：
same_streams = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:08.990644",
"Stream_3": "0:24:08.990644",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:12.118778",
"Stream_6": "0:24:10.075066"
} # note that "Stream_6" previously had a lower case 's'!
print_sync_half_matrix(half_sync_matrix)
# 1 2 3 4 5 6
# 1 T T F F T
# 2 T F F T
# 3 F F T
# 4 T F
# 5 F
记住matrix/print不包括对角线！这里的结果是正确的，正如输入所预期的那样。让我们打印出一些时间差异以获得更多情报，
for stream_key in same_stream:
print("Stream_1 ~ "+stream_key+": "+str(get_time_diff(same_streams["Stream_1"], same_streams[stream_key])))
.. 这很快表明您的时间戳已丢失其小数精度：
Stream_1 ~ Stream_5: 3.0
Stream_1 ~ Stream_4: 3.0
# ...
如果我们查看 datetime 的文档，我们会发现它将时间视为整数秒。因此，当您从 get_time_diff 函数中的 datetime 对象请求 seconds 时，微秒精度会丢失。简单地通过从 deltatime 方法 .total_seconds() 请求秒而不是..
来解决
所以，我试图通过 python 解决一些随机问题，但在逻辑上卡住了。这是问题所在： 我有多个视频及其 运行 时间或 运行ning 长度。现在，我想维护 2 个列表。 1 个列表如果 "synced"，另一个是 "non synced"。如果流的 运行 时间差小于或等于 2 秒，我们决定 "synced"。否则，它们不会同步。 如果我们有多个匹配的流，那么我们将采用匹配度最高的流 count/number.
我想出了一个非常 simple/slow 的方法来分割和配对这些文件。但是，当我得到不同的数据集时，我的逻辑失败了。
这是我写的:
from datetime import datetime
# same_streams_old = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:08.990644",
"Stream_3": "0:24:08.990644",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:12.118778",
"stream_6": "0:24:10.075066"
}
same_streams = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:12.118778",
"Stream_3": "0:23:11.057711",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:10.075066",
"Stream_6": "0:24:08.990644"
}
keys = []
values = []
final_synced_video_files = []
final_non_synced_video_files = []
def get_time_diff(episode_run_time, episode_time):
prev_episode_time = datetime.strptime(episode_run_time, '%H:%M:%S.%f')
current_episode_time = datetime.strptime(episode_time, '%H:%M:%S.%f')
time_diff = prev_episode_time - current_episode_time
if current_episode_time > prev_episode_time:
time_diff = current_episode_time - prev_episode_time
return float(time_diff.seconds)
for key, value in same_streams.items():
keys.append(key)
values.append(value)
for key in keys:
for _key in keys:
if key != _key:
diff = get_time_diff(same_streams[key], same_streams[_key])
if diff <= 1.5:
final_synced_video_files.append(key)
else:
pass
final_synced_video_files = list(set(final_synced_video_files))
final_non_synced_video_files = list(set(keys) - set(final_synced_video_files))
print("Synced Files : {0}".format(final_synced_video_files))
print("Non Synced Files : {0}".format(final_non_synced_video_files))
如您所见，匹配最多的流是 stream_1、stream_2、stream_3 和 stream_6。
我写的还没有比较最大计数。但是，在我处理这个问题时，我觉得这并不是真正有效的解决方法。有人有任何意见吗？
我尝试了一些关于重叠间隔的方法然后得到了这个：REPL LINK
但是，如果您 运行 同时查看 same_streams 词典，您会发现结果不是我想要达到的。任何帮助都会很棒。
编辑：
我需要获得彼此相差 2 秒的流。例如 ：
在 same_streams_old 中，期望的结果是流 1、2、3 和 6。但是，在字典 same_streams 中，期望的结果是流 2、4 和 5。
基本上，我需要查看哪些流可以 "muxed" 在一起，哪些不能混合。
好的，所以下面的打印例程可能有点乱，但请耐心等待，它们仅用于调试，完成后您可能不需要它们。我知道这是一个很长的答案，但请仔细阅读..
简答：
您的问题可能是因为当您从字符串转换为 datetime 时丢失了小数精度，后者将秒视为整数。但是，timedelta 对象有一个名为 total_seconds() 的方法，它确实提供亚秒级分辨率。有关详细信息，请参阅 this 或一般文档。只需将 get_time_diff() 的 return 语句更改为，
return float(time_diff.total_seconds())
长答案的动机：
我不确定你想用（非和）同步列表实现什么：你可能遇到流 a 同步的情况使用流 b，而流 c 与 d 同步，但 c 和 d not 与 a[=70= 同步] 和 b。他们都应该在你的 synced_list 中吗？根据你想对列表做什么，我会考虑使用下面描述的同步矩阵，而不是你的列表，因为它们会丢失很多信息。
长答案：
让我介绍一下同步矩阵的概念。它将完整描述您的哪些流相互同步：
THE SYNC MATRIX: A symmetric matrix; Cell (i,j) in the matrix is TRUE if, and only if, stream 'i' and 'j' are in sync. Else, the cell value is FALSE. Hence, the diagonal (.) is entirely TRUE because a stream is always in sync with itself.
1 2 3 4 ________ 1 | . T T F 2 | . T F 3 | . F 4 | ."T" is true, and "F" is false: obviously from the example drawing above, stream 1 is in sync with stream 2, but not in sync with stream 4.
创建这样一个同步矩阵对于您的示例来说非常简单：
def is_synced(key_1, key_2):
max_allowed_desync = 1.5
return max_allowed_desync > get_time_diff(same_streams[key_1], same_streams[key_2])
keys = same_streams.keys()
keys.sort() # VERY IMPORTANT, for the synced matrix to be constructed correctly; also make 's' uppercase for "stream_6" in OP.
# The complete matrix ..
full_sync_matrix = [[is_synced(k1,k2) for k2 in keys] for k1 in keys]
# We can optimize (memory usage) to only get the half matrix, since it's symmetric anyway; also excluding the diagonal.
half_sync_matrix = [[is_synced(k1,k2) for k2 in keys[curr+1:]] for curr,k1 in enumerate(keys)]
现在，让我们为 printing/displaying 同步矩阵实现两个函数：
# Print a HALFED sync matrix
def print_sync_half_matrix(sm):
string = ""
for i,row in enumerate(sm):
string += "\n" + " "*i*2
for col in row:
string += " " + ("T" if col else "F")
print(string)
# Print a COMPLETE sync_matrix
def print_sync_full_matrix(sm):
string = ""
for row in sm:
string += "\n"
for col in row:
string += " " + ("T" if col else "F")
print(string)
然后，对于您提供的数据集，我得到：
same_streams = {
"Stream_1": "0:24:08.925167",
"Stream_2": "0:24:08.990644",
"Stream_3": "0:24:08.990644",
"Stream_4": "0:24:12.118778",
"Stream_5": "0:24:12.118778",
"Stream_6": "0:24:10.075066"
} # note that "Stream_6" previously had a lower case 's'!
print_sync_half_matrix(half_sync_matrix)
# 1 2 3 4 5 6
# 1 T T F F T
# 2 T F F T
# 3 F F T
# 4 T F
# 5 F
记住matrix/print不包括对角线！这里的结果是正确的，正如输入所预期的那样。让我们打印出一些时间差异以获得更多情报，
for stream_key in same_stream:
print("Stream_1 ~ "+stream_key+": "+str(get_time_diff(same_streams["Stream_1"], same_streams[stream_key])))
.. 这很快表明您的时间戳已丢失其小数精度：
Stream_1 ~ Stream_5: 3.0
Stream_1 ~ Stream_4: 3.0
# ...
如果我们查看 datetime 的文档，我们会发现它将时间视为整数秒。因此，当您从 get_time_diff 函数中的 datetime 对象请求 seconds 时，微秒精度会丢失。简单地通过从 deltatime 方法 .total_seconds() 请求秒而不是..