合并ip地址的算法 [英] Algorithm to merge ip address

问题描述

我正在开发管理包含IP地址范围的纯文本的应用程序。

用户可以在范围内添加/删除ip。


删除ip的示例：

用户通过文本框输入的Ip：25.2.0.58

Ip范围容器：25.2.0.10 - 25.255.255.255


结果，（使用前面的例子）

25.2.0.10 - 25.2.0.57

25.2.0.59 - 25.255.255.255

正如您所看到的，用户输入的Ip已从中提取，并且已经有两个新的范围创建。


任何算法都可以这样做吗？


提前致谢。

Jota69

解决方案

这看起来像是一个搜索和拆分算法。我不确定你是如何实现的，因此我不确定问题出在哪里。


1.你如何持有范围？它们总是排序吗？

2.你如何搜索范围？

1.你好吗？持有范围？它们总是排序吗？

说明：

有10个列表，（lis1.txt，list2.txt，list3.txt等）。这个过程。

它们都包含IP范围。

现在你想象像防火墙这样的应用程序，它使用这些列表来过滤网络及其用户的有害ips。

嗯，Ipfile.txt文件是所有这些列表的总和。

显然，当添加到最终文件时，ip范围必须订购。 （Ipfile.txt）。


示例：


List1.txt

0.0.0.1-0.0.0.255

3.0.0.0-3.0.0.255

6.1.125.0-6.255.255.255

List2.txt

2.0.0.0-2.0.0.255

3.0.0.0-3.0.0.255

5.1.125.0-6.255.255.255


List3.txt

4.0.0.125-4.0.0.255

7.0.0.0-7.0.0.155

8.1.125.0-8.15.255.255


Ipfile.txt

0.0.0.1 - 0.0.0.255 - List1.txt

2.0.0.0 - 2.0.0.255 - List2.txt

3.0.0.0 - 3.0.0.255 - List2.txt

4.0.0.125 - 4.0.0.255 - List3.txt

5.1 .125.0 -6.255.255.255 - List2.txt

6.1.125.0 - 6.255.255.255 - List1.txt

7.0.0.0 - 7.0.0.155 - List3.txt

8.1.125.0 - 8.15.255.255 - List3.txt


如您所见，最终文件中的范围已正确排序。

为了让你有个主意，请阅读：

我的应用程序的用户，他们可以搜索，他们也可以添加和删除IP范围。

为此，只有您必须输入要删除的IP，然后按一个按钮。

当您按下删除按钮时，此按钮应执行一个能够执行以下算法的算法：

1 - 检查文件，如果有一系列值包括用户输入的ip。

2 - 如果有，那么算法应该删除ip范围的值。如上所述。（我的第一篇文章）。

2.你如何搜索范围？

我的朋友，问题的起源。我需要一个算法为我做。

从......

IPv4地址通常是用点十进制表示法表示（四个数字，每个数字范围从0到255，用点分隔，例如208.77.188.166）。每个部分代表8位地址，因此称为八位字节。在不常见的技术写作情况下，IPv4地址可以以十六进制，八进制或二进制表示形式呈现。在大多数表示中，每个八位字节都是单独转换的。

我得到八位字节分割（如下所示）ip地址，由用户输入。与每个文件行相同。 （分隔文件（ - ））。例如


208.77.188.166 - 208.77.188.183

208.77.188.195 - 208.77.188.206

208.77.188.210 - 208.77.188.255


Ip从范围中排除，（由用户输入）：208.77.188.236

范围容器：208.77.188.210 - 208.77.188.255

请注意，我们可以合并重叠和相邻的范围。 （我需要logaritm这样做）

例如208.77.188.166 - 208.77.188.255。


注意所有范围仅包含在一行中，从而节省了文件大小。 （我们正在谈论500.000行）


但是，让我们回到意味着目标=找到可能的范围容器，从中提取用户IP并删除它。
如何......？

创建两个新范围，例如


Ip从范围中排除，（由用户输入）： 208.77.188.236

范围容器：208.77.188.210 - 208.77.188.255


208.77.188.166 - 208.77.188.235

208.77.188.237 - 208.77.188.255


如果algoritm找到并删除重复的范围，也很好。


Firts，分割文件行。

208.77.188.166 - 208.77.188.235，你得到，IpStart和IpEnd。

IpStart = 208.77.188.166

IpEnd = 208.77.188.235

展开 | 选择 | Wrap | 行号

I am developing application that manage a plain text, containing ip address ranges.
User will be able to add/delete ip from ranges.

Example to delete ip:
Ip entered by user through a text box : 25.2.0.58
Ip Range container: 25.2.0.10 - 25.255.255.255

the Algorithm should determine whether there is in text file, a range that may contain the ip entered by the user. If so, remove it from container ip range.

Results, (using previous example )
25.2.0.10 - 25.2.0.57
25.2.0.59 - 25.255.255.255

As you can see, Ip entered by user it has been extracted from, and two
new ranges has been created.

Any Algorithm that can be able to do so?

Thanks in advance.
Jota69

解决方案

This seems like a search and split algorithm. I''m not sure how you''re implementing it, thus I''m not sure where the problem is.

1. How are you holding the ranges? Are they always sorted?
2. How are you searching the ranges?

1. How are you holding the ranges? Are they always sorted?

Explanation:
There are 10 lists,(lis1.txt, list2.txt, list3.txt and so on.) involved in the process.
They all contain IP ranges.
Now you imagine such an application like a firewall, that uses these lists to filter harmful ips for network, and its users.
Well, Ipfile.txt file is the sum of all these lists.
Obviously ip ranges have to order, when added to the final file. (Ipfile.txt).

Example:

List1.txt
0.0.0.1-0.0.0.255
3.0.0.0-3.0.0.255
6.1.125.0-6.255.255.255

List2.txt
2.0.0.0-2.0.0.255
3.0.0.0-3.0.0.255
5.1.125.0-6.255.255.255

List3.txt
4.0.0.125-4.0.0.255
7.0.0.0-7.0.0.155
8.1.125.0-8.15.255.255

Ipfile.txt
0.0.0.1 - 0.0.0.255 - List1.txt
2.0.0.0 - 2.0.0.255 - List2.txt
3.0.0.0 - 3.0.0.255 - List2.txt
4.0.0.125 - 4.0.0.255 - List3.txt
5.1.125.0 -6.255.255.255 - List2.txt
6.1.125.0 - 6.255.255.255 - List1.txt
7.0.0.0 - 7.0.0.155 - List3.txt
8.1.125.0 - 8.15.255.255 - List3.txt

As you can see the ranges in the final file, are properly sorted.
For you to have an idea, read this:
The user of my application, they will can search, they can also add and remove IP ranges.
To do this, only you must enter the ip you want to delete, and press a button.
When you press the button "delete", this button should execute an algorithm capable of:
1-check the file, if there is a range of values that includes user-entered ip .
2 - In case if there is, then algorithm it should remove the ip range of values. As explained above.(my firts post).

2. How are you searching the ranges?

That my friend, is the origin of the question. I need an algorithm to do it for me.

Since....

IPv4 addresses are usually represented in dot-decimal notation (four numbers, each ranging from 0 to 255, separated by dots, e.g. 208.77.188.166). Each part represents 8 bits of the address, and is therefore called an octet. In less common cases of technical writing, IPv4 addresses may be presented in hexadecimal, octal, or binary representations. In most representations each octet is converted individually.

I get octets splitting (as you point below) ip address, entered by user. and same with each file line. (delimited file(-)). e.g.

208.77.188.166 - 208.77.188.183
208.77.188.195 - 208.77.188.206
208.77.188.210 - 208.77.188.255

Ip to excluded from range, (entered by user) : 208.77.188.236
Range container: 208.77.188.210 - 208.77.188.255
Notice that we can to merge overlapping and adjacent ranges. (I need logaritm do it so)
e.g. 208.77.188.166 - 208.77.188.255.

Note all ranges are included in only one line, saving file size. (We are talking about 500.000 lines)

But, lets come back to mean target = Find possible range container, extract user ip from, and delete it.

How..?
Creating two new ranges, e.g.

Ip to excluded from range, (entered by user) : 208.77.188.236
Range container: 208.77.188.210 - 208.77.188.255

Results (I want to get, using any algoritm)
208.77.188.166 - 208.77.188.235
208.77.188.237 - 208.77.188.255

Also well be nice, if algoritm locate and delete duplicate ranges.

Firts at all, split file lines.
208.77.188.166 - 208.77.188.235, you get, IpStart and IpEnd.
IpStart = 208.77.188.166
IpEnd = 208.77.188.235

Expand|Select|Wrap|Line Numbers

这篇关于合并ip地址的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！