高校情報I パケット交換—分割したデータの経路と到着順から復元の条件を考える｜武蔵野個別指導塾

荷物追跡の文を番号順に組み直し、受信記録の欠落と重複を区別する手順を確かめます。

よくあるのは、高校生が荷物追跡のメッセージを受け取った順に並べ、元の文に戻らず困るという場面です。データを小さく分けて送るパケット交換では、到着した順番が送信した順番と異なることがあります。順番を示す情報を使って並べ直せば復元できる場合がありますが、一部が届いていなければ並べ直すだけでは完成しません。届いた個数だけで判断せず、番号の範囲と中身を照合します。

出方には、到着記録から元の文を復元する型、異なる経路と到着順を対応させる型、欠落や重複のある記録を調べて追加の条件を考える型があります。以下の記録は学習用に作ったもので、実際の配送や通信の測定結果ではありません。

分割した断片を区別する

パケット交換は、データを小さな単位に分け、ネットワークを通して運ぶ考え方です。パケットには運ぶデータのほか、配送に必要な情報が含まれます。途中の機器は宛先などを手掛かりに次の送り先を選びます。複数の通信がネットワークを共有できる一方、途中の混雑や経路の違いなどによって、送った順番どおりに届くとは限りません。

図1のように、送信側で分けた断片には、受信側が元の並びを判断するための情報が必要です。ここでは説明のため、各断片にメッセージの識別子、1から始まる通し番号、総数を付ける約束を作ります。これは学習用の設計であり、すべての実際のパケットが同じ項目を持つという意味ではありません。宛先は届け先を区別し、識別子はどのメッセージの断片かを区別し、番号はその中での位置を示します。総数は何番まで必要かを示します。

図1では、分割と情報の付加の後に運搬があり、受信側が番号を照合します。図は役割を表す概念図であり、特定の通信方式のパケット構造を示すものではありません。ここでの番号は元の文の順で決め、到着した順に振り直しません。後から到着順で番号を付けると、元の位置を示す手掛かりが失われます。

受信側は同じ識別子の断片を集め、総数が一致するかを確かめます。総数が4なら必要な番号は1、2、3、4です。これらがそれぞれ1個あり、内容が正しく対応しているという条件の下で、番号順につなげます。総数がなければ、例えば1から3まで届いても、3で終わりなのか4が欠けたのかを記録だけでは決められません。終端を別の方法で知らせる約束でもよいですが、必要な範囲を知る根拠は要ります。

順序逆転と欠落は別の状態です。2、1、3の順に届いても、必要な番号が1から3までそろっていれば、番号順に直せます。1、3だけなら2の内容は記録にありません。2を空欄のまま示すことはできますが、前後の意味から想像した文を受信したデータとして確定することはできません。待っている間に届く可能性と、記録の時点で届いていない事実も分けます。

同じ番号が2回届いた場合も、受信個数と異なる番号の個数は違います。同じ内容なら学習用の約束で重複を1個にまとめられますが、内容が食い違う場合はどちらが正しいか番号だけでは選べません。内容の破損や別のメッセージの混入も考えられます。今回の復元問題は、特に断らない限り、番号と内容の対応に誤りがないとします。実際には、確認や再送などを含む通信の仕組みが目的に応じて使われます。パケットに分けること自体が到着や順序を保証するわけではありません。

基本例題：荷物追跡の文を並べ直す

送信側は追跡メッセージ「荷物は」「中継所を」「出発しました」の順に3つへ分け、識別子A、総数3、番号1から3を付けました。番号1は「荷物は」、2は「中継所を」、3は「出発しました」です。経路は1と3が経路X、2が経路Yでした。受信記録は到着順に3、1、2です。各断片の内容は正しく、重複はありません。番号順に復元した文と、順序逆転と欠落の有無を答えてください。

まず到着記録の3、1、2を、送信番号として読みます。数字は時刻ではなく、元の文での位置です。到着順のままつなぐと「出発しました荷物は中継所を」となり、元の並びにはなりません。

次に総数3から、必要な番号を1、2、3と書きます。受信記録の番号と照合すると、1、2、3はいずれも1回あります。異なる番号は3個なので、必要な断片はそろっています。

番号順に内容を置くと、1は「荷物は」、2は「中継所を」、3は「出発しました」です。つなげた答えは「荷物は中継所を出発しました」です。3が1より先に到着しているので順序逆転はあります。必要な番号はそろっているため、この記録に欠落はありません。

図2のように、到着順の位置と番号順の位置を対応させます。復元した文を分割点で再び分けると、1から3の内容が送信側の表に戻ります。これで並べ直しの際に断片を入れ替えたり落としたりしていないことも確かめられます。

経路Xを通った1と3の間でも、3が先に届いています。同じ経路という条件だけから到着順を決めることはできません。また、経路Yを通った2が最後に届いたことから、経路Yが常に遅いと結論することもできません。この記録が示すのは今回の到着順と経路の対応です。図の線の長さを時間と見なす約束もありません。

標準例題：欠けた番号を特定する

別の追跡文を、識別子B、総数4の断片に分けます。1は「荷物を」、2は「営業所で」、3は「受け付け」、4は「ました」です。内容は正しく、同じ番号の重複はないとします。ある時点の到着記録は4、1、3でした。この時点での番号順の記録を空欄付きで示し、欠けた番号と、文を確定できるか答えてください。

総数4なので、必要な番号は1、2、3、4です。記録を番号ごとに調べると、1は「荷物を」、2は記録なし、3は「受け付け」、4は「ました」です。したがって番号順の記録は「荷物を｜空欄｜受け付け｜ました」、欠けた番号は2です。到着した番号は3個ですが、総数は4個なので1個足りません。

この時点では、空欄に何が入るか受信記録だけから確定できません。送信側の表が問題文に示されているため、この学習用問題を解く人は2の内容を知っています。しかし、その表を見られない受信側には、番号2の内容がまだありません。この区別をつけて「受信記録だけでは完成しない」と答えます。

後に2の「営業所で」が届き、同じ識別子と総数で内容も正しいと確認できたなら、1から4へ並べて「荷物を営業所で受け付けました」と復元できます。文をもう一度4断片に分ければ、元の表の1から4に対応します。逆に、待っても届かないときは、欠けた番号を知らせて再送を求めるなどの仕組みを別途用意する必要があります。受信記録にない内容を、到着順の並べ替えだけで作り出すことはできません。

到着記録は、どの時点までに届いたかを必ず明示します。後から2が届く可能性があるので、途中の記録から「永久に失われた」とは言えません。再送を求めた場合でも、その再送が必ず成功するとは限らず、完成を確認するには再び番号と内容を照合します。

発展例題：重複と識別子を点検する

2つの追跡文CとDを同時に送ります。Cは総数3で、1が「青い箱は」、2が「仕分け場に」、3が「到着」です。Dは総数2で、1が「赤い箱は」、2が「配送中」です。到着記録は順にCの2、Dの1、Cの1、Cの2、Dの2、Cの3です。Cの2の2回の内容は同じで、各番号の内容は正しいとします。同じ識別子と番号で内容が同一の重複は1個として扱います。各文と重複した断片を答えてください。

まず識別子で分けると、Cの番号は2、1、2、3、Dの番号は1、2です。全体の到着数は6個ですが、Cの2は2回あります。Cに必要な異なる番号は1、2、3の3個で、Dには1、2の2個が必要です。Cの2の重複を1個にまとめると、異なる断片はCが3個、Dが2個、合計5個です。

Cを番号順につなぐと「青い箱は仕分け場に到着」です。Dは「赤い箱は配送中」です。重複した断片はCの2で、内容は「仕分け場に」です。復元後のCを3つ、Dを2つに分け、各識別子と番号の送信側の表に戻して照合すると、必要な5種類に対応します。到着した6個から重複1個を除いた数とも一致します。

識別子を無視すると、Cの1とDの1が同じ位置の候補となり、別の文の断片を混ぜるおそれがあります。また、個数だけ見てCに4個届いたから完成と考えるのも危険です。例えばCの記録が1、2、2、2なら、4個届いても3がありません。反対に、Cの2が2回届いて内容が違う場合は、この問題の重複処理の条件を満たしません。番号が同じという理由だけで片方を捨てず、正しい内容を判定するための追加の仕組みが必要です。

誤答を直す：個数と番号は違う

総数3のメッセージEについて、到着した番号が1、1、3だったとします。ある解答は「3個届いたので1、2、3がそろい、復元できる」です。これは到着個数と、必要な番号の種類を混同しています。番号1の2個が同じ内容でも、番号2の内容を置き換えることはできません。

図3のように、受信記録の各番号を必要な番号と対応させると、1が重複し、2が見当たりません。正しくは「3個到着したが、番号2が未到着なので、この記録だけでは復元できない」です。1の2個の内容が一致するかも、重複をまとめる前に確認します。食い違うなら番号1の内容も確定できません。

別の誤りは、1、3、2と届いた記録を見て、順番が違うから2が欠けたとすることです。必要な番号が1から3で各1個なら、順序は違っても欠落はありません。順序の問題は並べ替えで直せますが、欠落は存在しない内容を補わなければ直せません。どちらの誤答も、必要な番号を先に書いて記録と照合すれば見分けられます。

経路の情報も、番号の代わりにはなりません。ある経路を通った断片が先に着いた例を見ても、別の断片が同じ順で届くとは限らないからです。必要なのは、今回与えられた記録から言えることと、追加の条件がなければ言えないことを分けることです。

練習問題

各問は独立した学習用の記録です。番号は1から始まり、各断片には識別子が付いています。問1から問4では総数も付けますが、問5では総数を受信側に知らせない条件で考えます。内容は正しく、同一番号の重複は内容が同じものとします。文を答えるときは番号順につなぎ、欠けた部分は「空欄」と書いてください。

1. 識別子F、総数3。1「箱は」、2「倉庫に」、3「あります」。到着順は2、3、1です。復元した文と、順序逆転および欠落の有無を答えてください。
2. 識別子G、総数4。1「荷札を」、2「確認し」、3「棚へ」、4「移動」。到着順は3、1、4です。番号順の記録を区切り付きで示し、欠けた番号を答えてください。
3. 識別子H、総数3。1「受付」、2「を」、3「完了」。到着順は1、3、1です。到着個数と異なる番号の個数、欠けた番号をそれぞれ答え、完成できるか説明してください。
4. 識別子Jの総数は2で、1「便は」、2「準備中」。識別子Kの総数は2で、1「箱は」、2「保管中」。到着順はJの2、Kの1、Jの1、Kの2です。それぞれの復元文を答え、識別子を使う理由を述べてください。
5. 識別子Lの番号1、2、3が各1個届きました。総数も終端を示す情報も受信側にはありません。この記録だけで完成と判断できるか、理由と、判断に役立つ追加情報を1つ答えてください。

練習問題の答えと解き方

1. 答えは「箱は倉庫にあります」です。総数3から必要な番号は1、2、3です。到着順2、3、1を番号順に直すと、1「箱は」、2「倉庫に」、3「あります」です。1が2より後に届いたので順序逆転はあります。各番号があるので欠落はありません。文を分け直すと元の3断片に戻ります。

2. 答えは「荷札を｜空欄｜棚へ｜移動」、欠けた番号は2です。必要な1から4と記録3、1、4を照合し、2がないとわかります。3個届いた事実は、2の中身が届いたことにはなりません。送信側の表には2の内容がありますが、受信記録に戻すと空欄のままです。後に正しい2が届けば「荷札を確認し棚へ移動」とつなげます。

3. 到着個数は3個、異なる番号は2個、欠けた番号は2です。番号1が2回、3が1回なので、必要な1、2、3のうち2がありません。重複した1を1個にまとめても2は現れず、受信記録だけでは完成できません。1と3を元の表に戻すと「受付」と「完了」が対応し、その間の断片が不足しています。

4. Jは「便は準備中」、Kは「箱は保管中」です。Jの記録を2、1から1、2へ、Kの記録を1、2のまま整理します。各文を2つに分け直すと、それぞれの識別子の1と2に戻ります。両方に番号1と2があるため、番号だけで集めると別の文を混ぜるおそれがあります。識別子によって同じ文に属する断片を集めます。

5. 完成とは判断できません。1から3がそろっていても、必要な範囲が1から3なのか、さらに4以降があるのかを区別できないためです。例えば送信側が付けた総数が3だと確認できれば、この問題の内容が正しいという条件の下で、必要な番号がそろったと判断できます。総数が4なら、同じ受信記録は4が欠けた状態です。受信記録を変えずに総数の条件を変えると結論が変わります。

覚えておくこと

• 到着順は元の順番と異なることがあります。
• 識別子と番号で、同じ文の断片を元の位置へ戻します。
• 総数などで必要な番号の範囲を知り、欠落と重複を調べます。
• パケットに分けること自体は到着や順序を保証しません。

つまずきを見分ける

届いた個数が総数と同じときにすぐ完成と答えるなら、番号の重複と欠落を表に書き出してみます。順序逆転を欠落と答えるなら、必要な番号がそれぞれ存在するかを先に確かめます。個別指導では、受信側が知っている情報に印を付け、送信側の表を見られない条件でも同じ結論になるかを説明してもらいます。到着記録の時点と、後に届いた場合を分けて話せるかも確認します。番号の照合が、文を元に戻す根拠になります。