4G近くある動画データを半分位に圧縮できる圧縮ソフトなどをご存知ないでしょうか...

データの圧縮には「可逆圧縮」と「不可逆圧縮」があります。


可逆圧縮は元の情報を完全に保持したまま容量を小さくする圧縮方法で、基本的にどんなデータでも圧縮できます。形式はzip、lzh、rar、7zなどがあります。
質問者さんが試した、4GBの動画ファイルが3.9GBになる方法はこれでしょう。
情報を完全に保持したまま圧縮するので、元データが「本質的に持っている情報量」より小さくすることは不可能です。言い換えれば、可逆圧縮には理論的な「圧縮できる限界」が存在するということです。
動画データは通常、この限界にかなり近いデータになります。よって可逆圧縮で節約できる余地はほとんどなく、4GBが3.9GBにしかならないのはごく当然のことです。


一方で不可逆圧縮は完全に元には戻らない圧縮方法で、データの性質をうまく利用して人間の目や耳では判別が難しい部分を削ることでデータ量を落とすものです。
動画であれば、画質や音質を犠牲にしてファイルサイズを大幅に落とすことができます。4GBを2GBにしたいならこちらを使うべきでしょう。
非可逆圧縮の方法は多岐にわたりますが、動画の場合「圧縮」よりも「動画変換」「エンコード」などと呼ばれることが多いです。この時使う圧縮形式は「コーデック」と呼ばれ、コーデックの種類によって人間の目や耳では判別が難しい部分の見分け方が違うので結果も変わってきます。基本的には新しいコーデックほど見分け方が巧くなり、同じファイルサイズなら画質劣化が目立たなくなります。


動画変換ソフトはフリーでも優秀なものが多数ありますが、とりあえずXMedia RecodeとSUPER©を勧めておきます。
http://www.gigafree.net/media/conv/
非可逆圧縮（エンコード）は可逆圧縮と違って様々なパラメータを指定する必要がありますが、主なものだけ説明しておきます。他にもたくさんあります（特に映像）。

【コンテナ】 映像と音声のデータを入れる箱のようなもの。
【コーデック】 映像と音声それぞれの圧縮形式。
これらをまとめて、コンテナAに映像コーデックBと音声コーデックCで圧縮されたデータを格納することをA（B＋C）などと表記します。お勧めは最新世代で高画質・高音質なmp4（H.264/AVC＋AAC）か、1世代前で互換性の高いavi（Xvid＋MP3）あたり。

映像関連パラメータ
【ビットレート】 1秒あたりのデータ量。大きいほど高画質＆ファイルサイズ大、画質にもっとも影響するパラメータ。
【レートモード】 ビットレートの割り振り方。動画は動きの激しいシーンほど同じ画質を維持するために必要なビットレートが大きくなるので、その処理の仕方を決めます。
ABR（平均）、CBR（一定）、VBR（品質）、2パスなどがありますが、よく分からないならABRが無難。2パスが最高品質ですが、変換時間は倍になります。
【フレームレート】 1秒あたりの画面を切り替える回数。大きいほど動きがなめらかになります。
特別な理由がない限り、元動画と同じフレームレートを指定するのが鉄則。
【解像度】 1フレームあたりの画面サイズ。縦×横で単位はピクセル数、大きいほど高精細になります（高画質とは限らない）。
元動画と同じが原則ですが、フレームレートより用途によって変更することが多いです（再生したいデバイスの制限に合わせるなど）。

音声関連パラメータ
【ビットレート】 映像と同じ。128kbps、192kbps、256kbps、320kbpsなどが一般的。
【レートモード】 映像と同じ。ただし映像ではあまり使われないCBRが音声ではよく使われる傾向があります。
【サンプリングレート】 1秒間に音声波形を短冊切りにする（量子化する）回数。映像のフレームレートに相当。
44.1kHzか48kHzが一般的。元動画と同じが原則です。

元動画の詳細情報を調べるには「コーデックチェッカー」を使います。
http://www.gigafree.net/media/codeccheck.html
ファイルサイズはほぼビットレート（映像と音声の合計値）に比例するので、コーデックチェッカーで元動画のビットレートを調べ、その半分のビットレートを指定して変換すれば、4GBの動画ファイルが2GBになるはずです。ビットレート以外のパラメータは元動画と同じが無難ですが、ベストとは限りません（動画の性質によります）。